Submission #744431

#TimeUsernameProblemLanguageResultExecution timeMemory
744431MODDICommuter Pass (JOI18_commuter_pass)C++14
0 / 100
410 ms16068 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back #define mp make_pair typedef long long ll; typedef pair<long long, long long> pll; typedef pair<int,int> pii; typedef vector<long long> vl; typedef vector<int> vi; int n, m, s1, e1, s2, e2; const ll inf = 1e18; vector<pii> G[100100]; vl dijkstra(int start){ vl dist(n); for(int i = 0; i < n; i++) dist[i] = inf; priority_queue<pair<ll, int>> pq; pq.push(mp(0, start)); dist[start] = 0; while(!pq.empty()){ int at = pq.top().second; pq.pop(); for(auto next : G[at]){ if(dist[next.first] > dist[at] + next.second){ dist[next.first] = dist[at] + next.second; pq.push(mp(-dist[next.first], next.first)); } } } return dist; } ll pair1[2][100100], pair2[2][100100]; pair<ll,ll> st[100100]; bool ok[100100]; pll comb(pll a, pll b) { return {min(a.first,b.first),min(a.second,b.second)}; } int main(){ cin>>n>>m>>s1>>e1>>s2>>e2; for(int i = 0; i < m; i++){ ll a, b, c; cin>>a>>b>>c; a--; b--; G[a].pb(mp(b,c)); G[b].pb(mp(a,c)); } // assert(false); vl arr = dijkstra(s1); for(int i = 0; i < n; i++) pair1[0][i] = arr[i]; arr = dijkstra(e1); for(int i = 0; i < n; i++) pair1[1][i] = arr[i]; arr = dijkstra(s2); for(int i = 0; i < n; i++) pair2[0][i] = arr[i]; arr = dijkstra(e2); for(int i = 0; i < n; i++) pair2[1][i] = arr[i]; // assert(false); for(int i = 0; i < n; i++) st[i] = {inf, inf}; ll ans = pair2[0][e2]; vector<pll> v; memset(ok, false, sizeof ok); for(int i = 0; i < n; i++){ if (pair1[0][i]+pair1[1][i] == pair1[0][e1]) { ok[i] = 1; v.pb({pair1[0][i],i}); } } sort(v.rbegin(),v.rend()); for (auto a: v) { for (auto t: G[a.second]) if (ok[t.first]) st[a.second] = comb(st[a.second],st[t.first]); ans = min(ans,min(st[a.second].first+pair2[1][a.second],st[a.second].second+pair2[0][a.second])); st[a.second] = comb(st[a.second],{pair2[0][a.second],pair2[1][a.second]}); } 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...