제출 #721546

#제출 시각아이디문제언어결과실행 시간메모리
721546Yell0Commuter Pass (JOI18_commuter_pass)C++17
15 / 100
265 ms22104 KiB
#include <bits/stdc++.h> #define f first #define s second using namespace std; typedef long long ll; typedef pair<ll,int> pii; const int MN=1e5+2; int N,M,S,T,U,V; ll du[MN],dv[MN],dis[MN],cu[MN],cv[MN]; bool vis[MN]; vector<pii> gr[MN]; int main() { ios::sync_with_stdio(0);cin.tie(0); cin>>N>>M>>S>>T>>U>>V; for(int i=1;i<=M;++i) { int u,v,w; cin>>u>>v>>w; gr[u].push_back(pii(w,v)); gr[v].push_back(pii(w,u)); } fill(du+1,du+1+N,1e18); memset(vis,0,sizeof(vis)); priority_queue<pii,vector<pii>,greater<pii>> pq; pq.push(pii(0,U)); du[U]=0; while(!pq.empty()) { int u=pq.top().s; ll d=pq.top().f; pq.pop(); if(vis[u]) continue; vis[u]=1; for(pii p:gr[u]) { int v=p.s; ll ed=p.f; if(!vis[v]&&d+ed<du[v]) { du[v]=d+ed; pq.push(pii(du[v],v)); } } } fill(dv+1,dv+1+N,1e18); memset(vis,0,sizeof(vis)); pq.push(pii(0,V)); dv[V]=0; while(!pq.empty()) { int u=pq.top().s; ll d=pq.top().f; pq.pop(); if(vis[u]) continue; vis[u]=1; for(pii p:gr[u]) { int v=p.s; ll ed=p.f; if(!vis[v]&&d+ed<dv[v]) { dv[v]=d+ed; pq.push(pii(dv[v],v)); } } } // S->T fill(dis+1,dis+1+N,1e18); fill(cu+1,cu+1+N,1e18); fill(cv+1,cv+1+N,1e18); memset(vis,0,sizeof(vis)); pq.push(pii(0,S)); dis[S]=0; cu[S]=du[S]; cv[S]=dv[S]; while(!pq.empty()) { int u=pq.top().s; ll d=pq.top().f; pq.pop(); if(vis[u]) continue; vis[u]=1; for(pii p:gr[u]) { int v=p.s; ll ed=p.f; if(!vis[v]&&d+ed<dis[v]) { if(d+ed<dis[v]) { dis[v]=d+ed; cu[v]=min(cu[u],du[v]); cv[v]=min(cv[u],dv[v]); pq.push(pii(dis[v],v)); } if(d+ed==dis[v]) { cu[v]=min({cu[u],cu[v],du[v]}); cv[v]=min({cv[u],cv[v],dv[v]}); } } } } cout<<min(cu[T]+cv[T],du[V])<<'\n'; 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...