제출 #824199

#제출 시각아이디문제언어결과실행 시간메모리
824199LeVanThucCommuter Pass (JOI18_commuter_pass)C++17
0 / 100
229 ms24496 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define fi first #define se second #define p(x,y) pair<ll,ll>(x,y) #define BIT(i,x) ((x>>i)&1) #define MASK(x) (1<<x) #define ld long double #define __builtin_popcount __builtin_popcountll #define pll pair<ll,ll> template<class T1,class T2> bool maximize(T1 &x,const T2 &y) { if(x<y) { x=y; return 1; } return 0; } template<class T1,class T2> bool minimize(T1 &x,const T2 &y) { if(x>y) { x=y; return 1; } return 0; } void online() { std::ios_base::sync_with_stdio(0); cin.tie(0); //#ifndef ONLINE_JUDGE // freopen("input.inp", "r", stdin); // freopen("output.out","w", stdout); //#else //#endif } const ll N=1e5+10; vector<pll> gr[N]; ll f[N],n,m,s,t,x,y,U[2*N],V[2*N],C[2*N],f1[N]; int main() { online(); cin>>n>>m>>s>>t>>x>>y; for(int i=1;i<=m;i++) { ll u,v,c; cin>>u>>v>>c; U[i]=u; V[i]=v; C[i]=c; gr[u].emplace_back(v,c); gr[v].emplace_back(u,c); } memset(f,0x3f,sizeof f); f[s]=0; priority_queue<pll,vector<pll>,greater<pll> > qq; qq.emplace(0,s); while(!qq.empty()) { auto [d,u]=qq.top(); qq.pop(); if(f[u]!=d) continue; for(auto [v,c]:gr[u]) { if(minimize(f[v],d+c)) qq.emplace(f[v],v); } } memset(f1,0x3f,sizeof f1); f1[t]=0; qq.emplace(0,t); while(!qq.empty()) { auto [d,u]=qq.top(); qq.pop(); if(f1[u]!=d) continue; for(auto [v,c]:gr[u]) { if(minimize(f1[v],d+c)) qq.emplace(f1[v],v); } } for(int i=1;i<=m;i++) { if(f[U[i]]+C[i]+f1[V[i]]==f[t]) { if(f[U[i]]<f[V[i]]) gr[U[i]].emplace_back(V[i],0); else gr[V[i]].emplace_back(U[i],0); } } memset(f,0x3f,sizeof f); f[x]=0; qq.emplace(0,x); while(!qq.empty()) { auto [d,u]=qq.top(); qq.pop(); if(f[u]!=d) continue; for(auto [v,c]:gr[u]) { if(minimize(f[v],d+c)) qq.emplace(f[v],v); } } ll ans=f[y]; memset(f,0x3f,sizeof f); f[y]=0; qq.emplace(0,y); while(!qq.empty()) { auto [d,u]=qq.top(); qq.pop(); if(f[u]!=d) continue; for(auto [v,c]:gr[u]) { if(minimize(f[v],d+c)) qq.emplace(f[v],v); } } minimize(ans,f[x]); cout<<ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...