제출 #341292

#제출 시각아이디문제언어결과실행 시간메모리
341292bigDuckCommuter Pass (JOI18_commuter_pass)C++14
100 / 100
942 ms33004 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, S, T, U, V; int Ds[100010], Du[100010], Dt[100010], Dv[100010]; bool v[100010]; vector<pii> g[100010]; pair<int ,pii> e[200010]; vector<pii> g2[100010]; void dijkstra(int s, vector<pii> g[], int D[], bool v[]){ multiset<pii> ms; ms.insert({0, s}); D[s]=0; while(!ms.empty()){ pii pr=(*ms.begin()); ms.erase(ms.begin()); int node=pr.sc, d=pr.ft; 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}); } else{ if((d+c)<D[u]){ D[u]=d+c; ms.erase(it); ms.insert({D[u], u}); } } } } } for(int i=1; i<=n;i++){ v[i]=false; } } void build_g2(){ for(int i=1; i<=m; i++){ int u=e[i].sc.ft, v=e[i].sc.sc, c=e[i].ft; if( (Ds[u]+c+Dt[v])==Ds[T] ){ g2[u].pb({v, c}); } if( (Ds[v]+c+Dt[u])==Ds[T] ){ g2[v].pb({u, c}); } } } int res=1e18; int mnu[100010], mnv[100010]; int dfsu(int s){ int dv=Dv[s]; v[s]=true; for(pii pr:g2[s]){ int u=pr.ft; dv=min(dv, Dv[u]); if(!v[u]){ dv=min(dfsu(u), dv);} dv=min(dv, mnv[u]); } res=min(res, Du[s]+dv); mnv[s]=dv; return dv; } int dfsv(int s){ int du=Du[s]; v[s]=true; for(pii pr:g2[s]){ int u=pr.ft; du=min(du, Du[u]); if(!v[u]){ du=min(dfsv(u), du);} du=min(du, mnu[u]); } res=min(res, du+Dv[s]); mnu[s]=du; return du; } int32_t main(){ INIT cin>>n>>m; cin>>S>>T; cin>>U>>V; for(int i=1; i<=m; i++){ int u, v, c; cin>>u>>v>>c; g[u].pb({v, c}); g[v].pb({u, c}); e[i]={c, {u, v}}; } dijkstra(S, g, Ds, v); dijkstra(T, g, Dt, v); dijkstra(U, g, Du, v); dijkstra(V, g, Dv, v); build_g2(); dfsu(S); for(int i=1; i<=n; i++){ v[i]=false; } dfsv(S); dfsu(T); for(int i=1; i<=n; i++){ v[i]=false; } dfsv(T); cout<<min(res, Du[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...