Submission #340736

#TimeUsernameProblemLanguageResultExecution timeMemory
340736bigDuckCommuter Pass (JOI18_commuter_pass)C++14
15 / 100
481 ms23532 KiB
#include<bits/stdc++.h> using namespace std; #define INIT ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); #define mp make_pair #define pb push_back #define ft first #define sc second #define ll long long #define pii pair<int, int> #define count_bits __builtin_popcount #define int ll int n, m, U, V, S, T; vector<pii> g[100010]; bool v[100010]; int D[100010]; int previous[100010]; void dijkstra(int s, int fin){ previous[s]=0; multiset<pii> ms; ms.insert({0, s}); while(!ms.empty()){ auto f=(*ms.begin()); ms.erase(ms.begin()); int node=f.sc, d=f.ft; if(node==fin){ break; } v[node]=true; for(pii pr:g[node]){ int u=pr.ft, c=pr.sc; if(!v[u]){ auto it=ms.find({D[u], u}); if(it==ms.end()){ D[u]=d+c; ms.insert({D[u], u}); previous[u]=node; } else{ if( (d+c)<D[u] ){ D[u]=d+c; ms.erase(it); ms.insert({D[u], u}); previous[u]=node; } } } } } for(int i=1; i<=n; i++){ v[i]=false; } return ; } void reconstruct(int fin){ int cr=fin; while(previous[cr]!=0){ int u=previous[cr]; g[u].pb({cr, 0}); g[cr].pb({u, 0}); cr=u; } } int32_t main(){ INIT cin>>n>>m; cin>>S>>T; cin>>U>>V; for(int i=1; i<=m; i++){ int a, b, c; cin>>a>>b>>c; g[a].pb({b,c}), g[b].pb({a, c}); } dijkstra(S, T); reconstruct(T); dijkstra(U, V); cout<<D[V]; 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...