제출 #1081542

#제출 시각아이디문제언어결과실행 시간메모리
1081542Muhammet사이버랜드 (APIO23_cyberland)C++17
49 / 100
86 ms48256 KiB
#include <bits/stdc++.h> #include "cyberland.h" // #include "stub.cpp" using namespace std; #define lb long double #define ll long long #define ff first #define ss second double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> a) { vector <pair<ll, ll>> v[n+5]; k = min(k,66); for(int i = 0; i < m; i++){ v[x[i]].push_back({y[i],c[i]}); v[y[i]].push_back({x[i],c[i]}); } vector <vector<lb>> dis(n+1, vector<lb> (k+1,1e18)); priority_queue <pair<lb,ll>> q; q.push({0,0}); dis[0][0] = 0; while(!q.empty()){ auto [w,x] = q.top(); q.pop(); w *= -1; if(w != dis[x][0]) continue; if(x == h) continue; for(auto [to,w1] : v[x]){ if((dis[to][0] > dis[x][0] + w1) or (a[to] == 0 and dis[to][0] != 0)){ dis[to][0] = dis[x][0] + w1; if(a[to] == 0) dis[to][0] = 0; q.push({-dis[to][0],to}); } } } lb ans = 1e18; bool tr = 0; for(int i = 1; i < k; i++){ q.push({0,0}); for(int j = 0; j < n; j++){ dis[j][i] = min(dis[j][i], dis[j][i-1]); } while(!q.empty()){ auto [w,x] = q.top(); q.pop(); w *= -1; if(w != dis[x][i]) continue; if(x == h) continue; for(auto [to,w1] : v[x]){ if(a[to] == 2){ lb w2 = w1; if(dis[to][i] > (dis[x][i-1] + w2) / 2){ dis[to][i] = (dis[x][i-1] + w2) / 2; q.push({-dis[to][i],to}); } } if((dis[to][i] > dis[x][i] + w1) or (a[to] == 0 and dis[to][i] != 0)){ dis[to][i] = dis[x][i] + w1; if(a[to] == 0) dis[to][i] = 0; q.push({-dis[to][i],to}); } } } } for(int i = 0; i <= k; i++){ ans = min(ans, dis[h][i]); } if(ans == 1e18) return -1; return ans; }

컴파일 시 표준 에러 (stderr) 메시지

cyberland.cpp: In function 'double solve(int, int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
cyberland.cpp:44:10: warning: unused variable 'tr' [-Wunused-variable]
   44 |     bool tr = 0;
      |          ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...