제출 #727773

#제출 시각아이디문제언어결과실행 시간메모리
727773fdnfksdCommuter Pass (JOI18_commuter_pass)C++14
100 / 100
517 ms68656 KiB
#include<bits/stdc++.h> #define TASKNAME "codeforce" #define pb push_back #define pli pair<ll,ll> #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[4][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]; ll deg[maxN]; vector<ll>rev[maxN];ll dp1[maxN],dp2[maxN]; ll ans=inf; void cal() { for(int i=1;i<=n;i++) deg[i]=0,rev[i].clear(),dp1[i]=inf,dp2[i]=inf; for(int i=1;i<=n;i++) { for(auto zz:g[i]) { deg[zz.fi]++; rev[zz.fi].pb(i); } } queue<int>q; for(int i=1;i<=n;i++) if(deg[i]==0) q.push(i); vector<ll> ver; while(!q.empty()) { ll u=q.front(); q.pop(); ver.pb(u); for(auto zz:g[u]) { deg[zz.fi]--; if(deg[zz.fi]==0) q.push(zz.fi); } } for(auto zz:ver) { dp1[zz]=d[2][zz]; for(auto vv:rev[zz]) { dp1[zz]=min(dp1[zz],dp1[vv]); } dp2[zz]=d[3][zz]; for(auto vv:rev[zz]) { dp2[zz]=min(dp2[zz],dp2[vv]); } ans=min(ans,dp1[zz]+d[3][zz]); ans=min(ans,dp2[zz]+d[2][zz]); } } 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}); } 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}); } } 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}); } 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}); } } dij(x,2); dij(y,3); for(int i=1;i<=n;i++) swap(adj[i],g[i]); cal(); for(int i=1;i<=n;i++) swap(ke[i],g[i]); cal(); cout << ans; } 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...