제출 #377199

#제출 시각아이디문제언어결과실행 시간메모리
377199smjleoCommuter Pass (JOI18_commuter_pass)C++14
15 / 100
407 ms23856 KiB
#include <bits/stdc++.h> #pragma GCC optimize("Ofast") #pragma GCC target("avx,avx2,fma") using namespace std; #define int long long #define nl '\n' #define io ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0) const int mod = 1000000007, mod2 = 998244353; // change this const int N = 100005; int n, m, s, t, u, v, du[N], dv[N], ds[N], dt[N], b1[N], b2[N]; vector< pair<int, int> > g[N]; signed main() { io; cin >> n >> m; cin >> s >> t; cin >> u >> v; for (int i=0; i<m; i++) { int a, b, c; cin >> a >> b >> c; g[a].push_back({b, c}); g[b].push_back({a, c}); } // distance from u priority_queue< pair<int, int>, vector<pair<int, int> >, greater<> > pq; for (int i=1; i<=n; i++) du[i] = dv[i] = ds[i] = dt[i] = b1[i] = b2[i] = 1e18; du[u] = 0; pq.push({0, u}); while (!pq.empty()) { auto cur = pq.top(); pq.pop(); int x = cur.second, d = cur.first; if (d > du[x]) continue; for (auto i : g[x]) { int nx = i.first, nd = d + i.second; // cout << "AA " << x << ' ' << nx << ' ' << nd << nl; if (du[nx] <= nd) continue; du[nx] = nd; pq.push({nd, nx}); } } // distance from v dv[v] = 0; pq.push({0, v}); while (!pq.empty()) { auto cur = pq.top(); pq.pop(); int x = cur.second, d = cur.first; if (d > dv[x]) continue; for (auto i : g[x]) { int nx = i.first, nd = d + i.second; if (dv[nx] <= nd) continue; dv[nx] = nd; pq.push({nd, nx}); } } // distance from s, update b1[N] also ds[s] = 0; b1[s] = dv[s]; pq.push({0, s}); while (!pq.empty()) { auto cur = pq.top(); pq.pop(); int x = cur.second, d = cur.first; if (d > ds[x]) continue; for (auto i : g[x]) { int nx = i.first, nd = d + i.second; if (ds[nx] <= nd) continue; ds[nx] = nd; b1[nx] = min(dv[nx], b1[x]); pq.push({nd, nx}); } } // distance from t, update b2[N] also dt[t] = 0; b2[t] = dv[t]; pq.push({0, t}); while (!pq.empty()) { auto cur = pq.top(); pq.pop(); int x = cur.second, d = cur.first; if (d > dt[x]) continue; for (auto i : g[x]) { int nx = i.first, nd = d + i.second; if (dt[nx] <= nd) continue; dt[nx] = nd; b2[nx] = min(dv[nx], b2[x]); pq.push({nd, nx}); } } int ans = du[v]; // for (int i=1; i<=n; i++) cout << du[i] << ' '; // cout << nl; for (int i=1; i<=n; i++) { // is it on the shortest path? if (ds[i] + dt[i] != ds[t]) continue; // no! ans = min(ans, du[i] + // go here first min(b1[i], b2[i]) // go to destination ); } cout << ans << nl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...