Submission #82609

#TimeUsernameProblemLanguageResultExecution timeMemory
82609hatuank97lhpCommuter Pass (JOI18_commuter_pass)C++14
100 / 100
915 ms76052 KiB
#include <bits/stdc++.h> #define LL long long #define F first #define S second #define mp make_pair using namespace std; void load() { #ifndef ONLINE_JUDGE freopen(".inp","r",stdin); freopen(".out","w",stdout); #endif // ONLINE_JUDGE } int n,m,a,b,c,d; const int N = 1e5 + 123; typedef pair < LL , int > II; vector < II > ed[N]; typedef pair < LL , II > IIII; LL dp[3][N],f[N][4],ans ; void dij(int s, int cs) { for (int i = 1 ; i <= n ; ++ i) dp[cs][i] = 1e18; dp[cs][s] = 0; priority_queue < II , vector < II > , greater < II > > q; q.push(mp(0,s)); while (!q.empty()) { II b = q.top(); q.pop(); if (b.F > dp[cs][b.S]) continue; for (II tmp : ed[b.S]) { int v = tmp.F, w = tmp.S; if (dp[cs][v] > b.F + w) dp[cs][v] = b.F + w, q.push(mp(dp[cs][v],v)); } } } void dij_2(int s) { for (int i = 1 ; i <= n ; ++ i) for (int j = 0 ; j < 4 ; ++ j) f[i][j] = 1e18; f[s][0] = 0; if (dp[1][s] + dp[2][s] == dp[2][a]) f[s][1] = 0; priority_queue < IIII , vector <IIII>, greater < IIII > > q; q.push(mp(f[s][0],mp(s,0))); q.push(mp(f[s][1],mp(s,1))); while (!q.empty()) { IIII b = q.top(); q.pop(); if (f[b.S.F][b.S.S] < b.F) continue; for (II tmp : ed[b.S.F]) { int v = tmp.F, w = tmp.S, typ = b.S.S; if (typ == 0) { if (f[v][0] > b.F + w) f[v][0] = b.F + w, q.push(mp(f[v][0], mp(v,0))); if (dp[1][v] + dp[2][v] == dp[2][a] && f[v][1] > b.F + w) f[v][1] = b.F + w, q.push(mp(f[v][1], mp(v,1))); } if (typ == 1) { if (f[v][0] > b.F + w) f[v][0] = b.F + w, q.push(mp(f[v][0], mp(v,0))); int u = b.S.F; if (dp[1][u] + dp[2][v] + w == dp[2][a] && f[v][2] > b.F) f[v][2] = b.F, q.push(mp(f[v][2],mp(v,2))); } if (typ == 2) { if (f[v][3] > b.F + w) f[v][3] = b.F + w, q.push(mp(f[v][3], mp(v,3))); int u = b.S.F; if (dp[1][u] + dp[2][v] + w == dp[2][a] && f[v][2] > b.F) f[v][2] = b.F, q.push(mp(f[v][2],mp(v,2))); } if (typ == 3) { if (f[v][3] > b.F + w) f[v][3] = b.F + w, q.push(mp(f[v][3], mp(v,3))); } } } ans = min(ans,min(f[d][0],f[d][1])); ans = min(ans,min(f[d][2],f[d][3])); return ; } void trungtt() { scanf("%d%d%d%d%d%d",&n,&m,&a,&b,&c,&d); for (int i = 1 ; i <= m ; ++ i) { int u,v,val; scanf("%d%d%d",&u,&v,&val); ed[u].push_back(mp(v,val)); ed[v].push_back(mp(u,val)); } ans = 1e18; dij(a,1); dij(b,2); dij_2(c); swap(a,b); dij(a,1); dij(b,2); dij_2(c); printf("%lld",ans); } int main() { //load(); trungtt(); return 0; }

Compilation message (stderr)

commuter_pass.cpp: In function 'void load()':
commuter_pass.cpp:11:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen(".inp","r",stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~
commuter_pass.cpp:12:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen(".out","w",stdout);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'void trungtt()':
commuter_pass.cpp:106:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d%d%d%d",&n,&m,&a,&b,&c,&d);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:109:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d",&u,&v,&val);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...