제출 #744440

#제출 시각아이디문제언어결과실행 시간메모리
744440MODDICommuter Pass (JOI18_commuter_pass)C++14
100 / 100
403 ms21280 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<pll, vector<pll>, greater<pll>>q; q.push({0, start}); dist[start] = 0; while(!q.empty()){ pll x = q.top(); q.pop(); if(dist[x.second] < x.first) continue; for(pii y : G[x.second]){ if(x.first + y.second < dist[y.first]){ dist[y.first] = x.first + y.second; q.push({dist[y.first], y.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; 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...