제출 #727737

#제출 시각아이디문제언어결과실행 시간메모리
727737fdnfksdCommuter Pass (JOI18_commuter_pass)C++14
15 / 100
389 ms51108 KiB
#include<bits/stdc++.h> #define TASKNAME "codeforce" #define pb push_back #define pli pair<int,int> #define fi first #define se second #define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); using namespace std; using ll=long long; const ll maxN=3e5; const ll inf=1e18; const ll mod=1e9+7; ll n,d[3][maxN]; bool vis[maxN]; vector<pli>g[maxN],adj[maxN],ke[maxN]; void dij(ll s,ll t) { for(int i=1;i<=n;i++) d[t][i]=inf,vis[i]=false; d[t][s]=0; priority_queue<pli,vector<pli>,greater<pli>>pq; pq.push({d[t][s],s}); while(!pq.empty()) { ll u=pq.top().se; pq.pop(); if(vis[u]==true) continue; vis[u]=true; for(auto vv:g[u]) { ll v=vv.fi; ll w=vv.se; if(d[t][v]>d[t][u]+w) { d[t][v]=d[t][u]+w; pq.push({d[t][v],v}); } } } } ll m,s,t,x,y; struct qq { ll u,v,w; }a[maxN]; void solve() { cin >> n >> m; cin >> s >> t; cin >> x >> y; for(int i=1;i<=m;i++) { ll u,v,w; cin >> u >> v >> w; a[i].u=u; a[i].v=v; a[i].w=w; g[u].pb({v,w}); g[v].pb({u,w}); } dij(s,0); dij(t,1); for(int i=1;i<=m;i++) { if(d[0][a[i].u]+d[1][a[i].v]+a[i].w==d[0][t]) { adj[a[i].u].pb({a[i].v,0}); adj[a[i].v].pb({a[i].u,a[i].w}); } else if(d[0][a[i].v]+d[1][a[i].u]+a[i].w==d[0][t]) { adj[a[i].v].pb({a[i].u,0}); adj[a[i].u].pb({a[i].v,a[i].w}); } else { adj[a[i].u].pb({a[i].v,a[i].w}); adj[a[i].v].pb({a[i].u,a[i].w}); } } for(int i=1;i<=m;i++) { if(d[0][a[i].u]+d[1][a[i].v]+a[i].w==d[0][t]) { ke[a[i].v].pb({a[i].u,0}); ke[a[i].u].pb({a[i].v,a[i].w}); } else if(d[0][a[i].v]+d[1][a[i].u]+a[i].w==d[0][t]) { ke[a[i].u].pb({a[i].v,0}); ke[a[i].v].pb({a[i].u,a[i].w}); } else { ke[a[i].u].pb({a[i].v,a[i].w}); ke[a[i].v].pb({a[i].u,a[i].w}); } } for(int i=1;i<=n;i++) swap(adj[i],g[i]); ll ans=inf; dij(x,0); ans=d[0][y]; for(int i=1;i<=n;i++) swap(ke[i],g[i]); dij(x,0); ans=min(ans,d[0][y]); cout << ans <<'\n'; } int main() { fastio //freopen(TASKNAME".INP","r",stdin); //freopen(TASKNAME".OUT","w",stdout); solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...