Submission #817977

#TimeUsernameProblemLanguageResultExecution timeMemory
817977OAleksaCommuter Pass (JOI18_commuter_pass)C++14
100 / 100
323 ms29628 KiB
#include <bits/stdc++.h> //#include "factories.h" //#include "wall.h" #define f first #define s second #define int long long using namespace std; const int maxn = 1e5 + 69; vector<pair<int, int>> g[maxn]; int n, m, s, t, u, v; const int inf = 1e18; vector<int> d(maxn, inf); vector<int> ds(maxn, inf), dt(maxn, inf); vector<int> du(maxn, inf), dv(maxn, inf); vector<int> in(maxn, inf), out(maxn, inf); signed main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int tt = 1; //cin >> tt; while(tt--) { cin >> n >> m >> s >> t >> 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}); } ds[s] = du[u] = dv[v] = dt[t] = d[s] = 0; priority_queue<pair<int, int>> pq; pq.push({0, s}); while(!pq.empty()) { auto u = pq.top(); pq.pop(); for(auto v : g[u.s]) { if(ds[v.f] <= ds[u.s] + v.s) continue; ds[v.f] = ds[u.s] + v.s; pq.push({-ds[v.f], v.f}); } } pq.push({0, t}); while(!pq.empty()) { auto u = pq.top(); pq.pop(); for(auto v : g[u.s]) { if(dt[v.f] <= dt[u.s] + v.s) continue; dt[v.f] = dt[u.s] + v.s; pq.push({-dt[v.f], v.f}); } } pq.push({0, u}); while(!pq.empty()) { auto u = pq.top(); pq.pop(); for(auto v : g[u.s]) { if(du[v.f] <= du[u.s] + v.s) continue; du[v.f] = du[u.s] + v.s; pq.push({-du[v.f], v.f}); } } pq.push({0, v}); while(!pq.empty()) { auto u = pq.top(); pq.pop(); for(auto v : g[u.s]) { if(dv[v.f] <= dv[u.s] + v.s) continue; dv[v.f] = dv[u.s] + v.s; pq.push({-dv[v.f], v.f}); } } int ans = du[v]; for(int i = 1;i <= n;i++) in[i] = out[i] = inf; function<void(int)> dfs1 = [&](int v) { if(in[v] != inf || ds[v] + dt[v] != ds[t]) return; in[v] = du[v]; for(auto u : g[v]) { if(ds[u.f] == ds[v] + u.s) { dfs1(u.f); in[v] = min(in[u.f], in[v]); } } ans = min(ans, in[v] + dv[v]); }; function<void(int)> dfs2 = [&](int v) { if(in[v] != inf || ds[v] + dt[v] != ds[t]) return; in[v] = du[v]; for(auto u : g[v]) { if(dt[u.f] == dt[v] + u.s) { dfs2(u.f); in[v] = min(in[u.f], in[v]); } } ans = min(ans, in[v] + dv[v]); }; dfs1(s); for(int i = 1;i <= n;i++) in[i] = inf; dfs2(t); cout << ans; } 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...