제출 #1009806

#제출 시각아이디문제언어결과실행 시간메모리
1009806makanhuliaCommuter Pass (JOI18_commuter_pass)C++17
0 / 100
322 ms262144 KiB
#include<bits/stdc++.h> #define int long long #define pii pair<int, int> #define ppi pair<pii, int> #define pu push_back #define fi first #define se second using namespace std; const int maxn = 1e5; const int inf = 1e15; int n, m, s, t, u, v; int a[maxn+5], b[maxn+5], c[maxn+5], du[maxn+5], dv[maxn+5], ds[maxn+5], dt[maxn+5], dpsv[maxn+5], dptv[maxn+5]; vector<pii> adj[maxn+5]; priority_queue<ppi, vector<ppi>, greater<ppi>> p; priority_queue<pii, vector<pii>, greater<pii>> q; signed main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin >> n >> m >> s >> t >> u >> v; for (int i=1; i<=m; i++) { cin >> a[i] >> b[i] >> c[i]; adj[a[i]].pu({b[i], c[i]}); adj[b[i]].pu({a[i], c[i]}); } for (int i=1; i<=n; i++) { du[i] = dv[i] = ds[i] = dt[i] = inf; } // dijkstra u to all nodes and v to all nodes du[u] = 0; q.push({0, u}); while (!q.empty()) { int now = q.top().se, dis = q.top().fi; q.pop(); if (dis > du[now]) continue; for (auto i: adj[now]) { if (dis + i.se >= du[i.fi]) continue; du[i.fi] = dis + i.se; q.push({du[i.fi], i.fi}); } } dv[v] = 0; q.push({0, v}); while (!q.empty()) { int now = q.top().se, dis = q.top().fi; q.pop(); if (dis > dv[now]) continue; for (auto i: adj[now]) { if (dis + i.se >= dv[i.fi]) continue; dv[i.fi] = dis + i.se; q.push({dv[i.fi], i.fi}); } } // do the same for nodes s and t ds[s] = 0; q.push({0, s}); while (!q.empty()) { int now = q.top().se, dis = q.top().fi; q.pop(); if (dis > ds[now]) continue; for (auto i: adj[now]) { if (dis + i.se >= ds[i.fi]) continue; ds[i.fi] = dis + i.se; q.push({ds[i.fi], i.fi}); } } dt[t] = 0; q.push({0, t}); while (!q.empty()) { int now = q.top().se, dis = q.top().fi; q.pop(); if (dis > dt[now]) continue; for (auto i: adj[now]) { if (dis + i.se >= dt[i.fi]) continue; dt[i.fi] = dis + i.se; q.push({dt[i.fi], i.fi}); } } for (int i=1; i<=n; i++) { dpsv[i] = dptv[i] = dv[i]; } // update q.push({0, t}); while (!q.empty()) { int now = q.top().se, dis = q.top().fi; q.pop(); for (auto i: adj[now]) { if (dis + i.se > dt[i.fi] || ds[i.fi] + dt[i.fi] > ds[t]) continue; // cout << i.fi << " to " << now << " is an edge in a shortest path from s-t" << endl; dptv[i.fi] = min(dptv[i.fi], dptv[now]); q.push({dt[i.fi], i.fi}); } } q.push({0, s}); while (!q.empty()) { int now = q.top().se, dis = q.top().fi; q.pop(); for (auto i: adj[now]) { if (dis + i.se > ds[i.fi] || ds[i.fi] + dt[i.fi] > ds[t]) continue; // cout << i.fi << " to " << now << " is an edge in a shortest path from s-t" << endl; dpsv[i.fi] = min(dpsv[i.fi], dpsv[now]); q.push({ds[i.fi], i.fi}); } } // // for (int i=1; i<=n; i++) { // cout << "dv[" << i << "]: " << dv[i] << endl; // } // int ans = du[v]; for (int i=1; i<=n; i++) { if (ds[i] + dt[i] > ds[t]) continue; ans = min(ans, du[i] + min(dpsv[i], dptv[i])); } cout << ans << endl; return 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...