Submission #500100

#TimeUsernameProblemLanguageResultExecution timeMemory
500100buidangnguyen05Commuter Pass (JOI18_commuter_pass)C++14
16 / 100
350 ms15736 KiB
/* input */ #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e5 + 10; int n, m; vector<pair<int, int>> adj[N]; pair<vector<ll>, vector<int>> dijkstra(int s) { vector<ll> d(n + 2, 1e15); vector<int> order; d[s] = 0; priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> q; q.push(make_pair(d[s], s)); while(!q.empty()) { ll dist; int x; tie(dist, x) = q.top(); q.pop(); if(dist != d[x]) continue; order.push_back(x); for(pair<int, int> i : adj[x]) { int v, w; tie(v, w) = i; if(d[v] > d[x] + w) { d[v] = d[x] + w; q.push(make_pair(d[v], v)); } } } return make_pair(d, order); } signed main() { cin.tie(0)->sync_with_stdio(0); //freopen("task.inp", "r", stdin); //freopen("task.out", "w", stdout); int s, t, u, v; cin >> n >> m >> s >> t >> u >> v; for(int i = 1; i <= m; ++i) { int x, y, w; cin >> x >> y >> w; adj[x].push_back(make_pair(y, w)); adj[y].push_back(make_pair(x, w)); } vector<ll> fu = dijkstra(u).first; vector<ll> fv = dijkstra(v).first; vector<ll> ft = dijkstra(t).first; vector<ll> fs; vector<int> order; tie(fs, order) = dijkstra(s); ll res = fu[v]; for(int turn = 0; turn < 2; ++turn) { vector<ll> f(n + 2, 1e15); f[s] = fu[s]; for(int x : order) { res = min(res, f[x] + fv[x]); for(pair<int, int> e : adj[x]) { int i, w; tie(i, w) = e; if(fs[i] + ft[i] != fs[t]) continue; f[i] = min(f[i], f[x]); f[i] = min(f[i], fu[x]); } } fu.swap(fv); } cout << res << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...