제출 #855951

#제출 시각아이디문제언어결과실행 시간메모리
855951phoenix0423Commuter Pass (JOI18_commuter_pass)C++17
100 / 100
350 ms29160 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll, ll> pll; #define fastio ios::sync_with_stdio(false), cin.tie(0) #define pb push_back #define eb emplace_back const int maxn = 2e5 + 5; const int N = 1e9 + 7; const ll INF = 1e18; vector<pll> adj[maxn]; int n, m, s, t, u, v; ll dist[maxn][6]; void dijkstra(int st, int id){ for(int i = 0; i < n; i++) dist[i][id] = INF; dist[st][id] = 0; priority_queue<pll, vector<pll>, greater<pll>> q; q.push({0, st}); while(!q.empty()){ auto [d, pos] = q.top(); q.pop(); if(dist[pos][id] != d) continue; for(auto [x, w] : adj[pos]){ if(dist[x][id] > dist[pos][id] + w){ dist[x][id] = dist[pos][id] + w; q.push({dist[x][id], x}); } } } } void dijkstra2(int dir, int id){ priority_queue<pll, vector<pll>, greater<pll>> q; for(int i = 0; i < n; i++) dist[i][id] = dist[i][2], q.push({dist[i][id], i}); while(!q.empty()){ auto [d, pos] = q.top(); q.pop(); if(dist[pos][id] != d) continue; for(auto [x, w] : adj[pos]){ if(dist[pos][dir] + dist[x][dir ^ 1] + w == dist[t][0]){ if(dist[x][id] > dist[pos][id]){ dist[x][id] = dist[pos][id]; q.push({dist[x][id], x}); } } } } } int main(void){ fastio; cin>>n>>m>>s>>t>>u>>v; s--, t--, u--, v--; for(int i = 0; i < m; i++){ int a, b, c; cin>>a>>b>>c; a--, b--; adj[a].eb(b, c); adj[b].eb(a, c); } dijkstra(s, 0); dijkstra(t, 1); dijkstra(v, 2); dijkstra2(0, 3); dijkstra2(1, 4); dijkstra(u, 5); ll ans = INF; for(int i = 0; i < n; i++) ans = min(ans, dist[i][5] + min(dist[i][3], dist[i][4])); cout<<ans<<"\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...