제출 #1036387

#제출 시각아이디문제언어결과실행 시간메모리
1036387ThommyDBCommuter Pass (JOI18_commuter_pass)C++17
0 / 100
218 ms17164 KiB
#include<bits/stdc++.h> using namespace std; int n, m, s, t, u, v, ans; vector<vector<pair<int, int>>> adj; vector<int> dist_u, dist_v; vector<bool> visited; void get_dist(int start, vector<int>& dist){ dist.resize(n+1, 1e9); dist[start]=0; fill(visited.begin(), visited.end(), false); priority_queue<pair<int, int>> pq; pq.push({dist[start], start}); while(!pq.empty()){ int a = pq.top().second; int c = -pq.top().first; pq.pop(); if(visited[a])continue; visited[a]=true; for(auto x : adj[a]){ if(dist[a]+x.second < dist[x.first]){ dist[x.first] = dist[a]+x.second; pq.push({-dist[x.first], x.first}); } } } } signed main(){ cin >> n >> m >> s >> t >> u >> v; adj.resize(n+1); visited.resize(n+1); for(int i = 0; i < m; i++){ int a, b, c; cin >> a >> b >> c; adj[a].push_back({b,c}); adj[b].push_back({a,c}); } get_dist(u, dist_u); get_dist(v, dist_v); ans = dist_u[v]; int a = s, b=t; vector<int> dist_a, dp_c, dp_d; dist_a.resize(n+1, 1e9); dp_c.resize(n+1, 1e9); dp_d.resize(n+1, 1e9); dist_a[a]=0; fill(visited.begin(), visited.end(), false); priority_queue<pair<int, pair<int, int>>> pq; pq.push({0, {a, 0}}); while (!pq.empty()) { int c = -pq.top().first; int d = pq.top().second.first; int e = pq.top().second.second; pq.pop(); if(!visited[d]){ visited[d]=true; dp_c[d]=min(dp_c[e],dist_u[d]); dp_d[d]=min(dp_d[e],dist_v[d]); for(auto x : adj[d]){ if(dist_a[d] + x.second < dist_a[x.first]){ dist_a[x.first]=dist_a[d]+x.second; pq.push({-dist_a[x.first], {x.first, d}}); } } } else{ if(c==dist_a[d] && (min(dp_c[e],dist_u[d]) + min(dp_d[e], dist_v[d]) <= dp_c[d]+dp_d[d])){ dp_c[d]=min(dp_c[e],dist_u[d]); dp_d[d]=min(dp_d[e], dist_v[d]); } } } ans = min(ans, dp_c[b] + dp_d[b]); cout << ans << "\n"; }

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

commuter_pass.cpp: In function 'void get_dist(int, std::vector<int>&)':
commuter_pass.cpp:19:13: warning: unused variable 'c' [-Wunused-variable]
   19 |         int c = -pq.top().first;
      |             ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...