제출 #782990

#제출 시각아이디문제언어결과실행 시간메모리
782990borisAngelovCommuter Pass (JOI18_commuter_pass)C++17
100 / 100
306 ms21108 KiB
#include <bits/stdc++.h> using namespace std; const int maxn = 100005; const long long inf = (1LL << 60); int n, m; int s, t, u, v; struct edge { int to; long long w; }; vector<edge> g[maxn]; long long dist_from_u[maxn]; long long dist_from_v[maxn]; void shortest_path(int source, long long dist[]) { for (int i = 1; i <= n; ++i) { dist[i] = inf; } dist[source] = 0LL; priority_queue<pair<long long, int>> pq; pq.push(make_pair(0LL, source)); while (!pq.empty()) { int node = pq.top().second; long long curr = -pq.top().first; pq.pop(); for (int i = 0; i < g[node].size(); ++i) { long long path = curr + g[node][i].w; int to = g[node][i].to; if (dist[to] > path) { dist[to] = path; pq.push(make_pair(-path, to)); } } } } long long dp_u[maxn]; long long dp_v[maxn]; bool visited[maxn]; long long dist[maxn]; long long ans = inf; void calc_dp(long long source, long long sink) { for (int i = 1; i <= n; ++i) { visited[i] = false; dist[i] = inf; dp_u[i] = inf; dp_v[i] = inf; } priority_queue<pair<long long, pair<int, int>>> pq; pq.push(make_pair(0LL, make_pair(source, 0))); dp_u[0] = inf; dp_v[0] = inf; while (!pq.empty()) { long long curr = -pq.top().first; int node = pq.top().second.first; int par = pq.top().second.second; pq.pop(); if (visited[node] == false) { dist[node] = curr; visited[node] = true; dp_u[node] = min(dist_from_u[node], dp_u[par]); dp_v[node] = min(dist_from_v[node], dp_v[par]); for (int i = 0; i < g[node].size(); ++i) { long long path = curr + g[node][i].w; int to = g[node][i].to; if (visited[to] == false) { pq.push(make_pair(-path, make_pair(to, node))); } } } else if (curr == dist[node]) { if (min(dist_from_u[node], dp_u[par]) + min(dist_from_v[node], dp_v[par]) <= dp_u[node] + dp_v[node]) { dp_u[node] = min(dist_from_u[node], dp_u[par]); dp_v[node] = min(dist_from_v[node], dp_v[par]); } } } ans = min(ans, dp_u[sink] + dp_v[sink]); } void fastIO() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); } int main() { fastIO(); cin >> n >> m >> s >> t >> u >> v; for (int i = 1; i <= m; ++i) { int x, y; cin >> x >> y; long long w; cin >> w; g[x].push_back({y, w}); g[y].push_back({x, w}); } shortest_path(u, dist_from_u); shortest_path(v, dist_from_v); ans = dist_from_u[v]; calc_dp(s, t); calc_dp(t, s); cout << ans << endl; return 0; }

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

commuter_pass.cpp: In function 'void shortest_path(int, long long int*)':
commuter_pass.cpp:41:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         for (int i = 0; i < g[node].size(); ++i)
      |                         ~~^~~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'void calc_dp(long long int, long long int)':
commuter_pass.cpp:95:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |             for (int i = 0; i < g[node].size(); ++i)
      |                             ~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...