Submission #173023

#TimeUsernameProblemLanguageResultExecution timeMemory
173023arnold518Commuter Pass (JOI18_commuter_pass)C++14
100 / 100
791 ms38772 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int MAXN = 1e5; const ll INF = 1e18; int N, M, S, T, U, V; ll DU[MAXN+10], DV[MAXN+10], DS[MAXN+10], DT[MAXN+10], dp1[MAXN+10][2], dp2[MAXN+10][2]; vector<pll> adj[MAXN+10]; vector<int> adj2[MAXN+10], adj3[MAXN+10]; struct Queue { ll v, w; bool operator < (const Queue& p) const { return w>p.w; } }; void dijk(int s, ll* D) { int i, j; for(i=1; i<=N; i++) D[i]=INF; priority_queue<Queue> PQ; PQ.push({s, 0}); while(!PQ.empty()) { Queue T=PQ.top(); PQ.pop(); if(D[T.v]<=T.w) continue; D[T.v]=T.w; for(pii nxt : adj[T.v]) { PQ.push({nxt.first, nxt.second+T.w}); } } } bool vis[MAXN+10]; vector<int> order; void dfs(int now, vector<int> *adj0) { vis[now]=true; for(int nxt : adj0[now]) if(!vis[nxt]) dfs(nxt, adj0); order.push_back(now); } int main() { int i, j; scanf("%d%d%d%d%d%d", &N, &M, &S, &T, &U, &V); for(i=1; i<=M; i++) { int u, v, w; scanf("%d%d%d", &u, &v, &w); adj[u].push_back({v, w}); adj[v].push_back({u, w}); } dijk(U, DU); dijk(V, DV); dijk(S, DS); dijk(T, DT); for(i=1; i<=N; i++) for(pll nxt : adj[i]) if(DS[i]+nxt.second==DS[nxt.first]) adj2[i].push_back(nxt.first); for(i=1; i<=N; i++) for(pll nxt : adj[i]) if(DT[i]+nxt.second==DT[nxt.first]) adj3[i].push_back(nxt.first); memset(vis, 0, sizeof(vis)); order.clear(); dfs(S, adj2); reverse(order.begin(), order.end()); for(i=1; i<=N; i++) dp1[i][0]=dp1[i][1]=dp2[i][0]=dp2[i][1]=1e17; for(int now : order) { dp1[now][0]=min(dp1[now][0], DU[now]); dp1[now][1]=min(dp1[now][1], DV[now]); for(int nxt : adj2[now]) { dp1[nxt][0]=min(dp1[nxt][0], dp1[now][0]); dp1[nxt][1]=min(dp1[nxt][1], dp1[now][1]); } } memset(vis, 0, sizeof(vis)); order.clear(); dfs(T, adj3); reverse(order.begin(), order.end()); for(int now : order) { dp2[now][0]=min(dp2[now][0], DU[now]); dp2[now][1]=min(dp2[now][1], DV[now]); for(int nxt : adj3[now]) { dp2[nxt][0]=min(dp2[nxt][0], dp2[now][0]); dp2[nxt][1]=min(dp2[nxt][1], dp2[now][1]); } } ll ans=DU[V]; for(i=1; i<=N; i++) if(DS[i]+DT[i]==DS[T]) { ans=min(ans, dp1[i][0]+dp2[i][1]); ans=min(ans, dp1[i][1]+dp2[i][0]); } printf("%lld", ans); }

Compilation message (stderr)

commuter_pass.cpp: In function 'void dijk(int, ll*)':
commuter_pass.cpp:24:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:52:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
commuter_pass.cpp:54: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, &S, &T, &U, &V);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:58:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &u, &v, &w);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...