제출 #875801

#제출 시각아이디문제언어결과실행 시간메모리
875801Beerus13Commuter Pass (JOI18_commuter_pass)C++14
100 / 100
244 ms24112 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define pii pair<ll, int> #define fi first #define se second const int ar = 1e5 + 5; int n, m, u, v, s, t; ll dp[ar][2], dis[ar][2], d[ar]; vector<pii> adj[ar]; ll ans = 1e18; void dijktra(int u, int c) { priority_queue<pii, vector<pii>, greater<pii>> q; q.push({0, u}); dp[u][c] = 0; while(q.size()) { int vt = q.top().se; ll kc = q.top().fi; q.pop(); if(kc > dp[vt][c]) continue; for(auto x : adj[vt]) { if(dp[x.se][c] > dp[vt][c] + x.fi) { dp[x.se][c] = dp[vt][c] + x.fi; q.push({dp[x.se][c], x.se}); } } } } void dijktra2(int u) { memset(dis, 0x3f, sizeof(dis)); memset(d, 0x3f, sizeof(d)); priority_queue<pii, vector<pii>, greater<pii>> q; q.push({0, u}); dis[u][0] = dp[u][0]; dis[u][1] = dp[u][1]; d[u] = 0; while(q.size()) { int vt = q.top().se, pa = q.top().se; ll kc = q.top().fi; q.pop(); if(kc > d[vt]) continue; for(auto x : adj[vt]) { if(d[x.se] > d[vt] + x.fi) { d[x.se] = d[vt] + x.fi; dis[x.se][0] = min(dp[x.se][0], dis[vt][0]); dis[x.se][1] = min(dp[x.se][1], dis[vt][1]); q.push({d[x.se], x.se}); } else if(d[x.se] == d[vt] + x.fi) { if(min(dp[x.se][0], dis[vt][0]) + min(dp[x.se][1], dis[vt][1]) <= dis[x.se][0] + dis[x.se][1]) { dis[x.se][0] = min(dp[x.se][0], dis[vt][0]); dis[x.se][1] = min(dp[x.se][1], dis[vt][1]); } } } } } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m >> s >> t >> u >> v; for(int i = 1; i <= m; ++i) { int x, y, w; cin >> x >> y >> w; adj[x].push_back({w, y}); adj[y].push_back({w, x}); } memset(dp, 0x3f, sizeof(dp)); dijktra(u, 0); dijktra(v, 1); ans = dp[v][0]; dijktra2(s); ans = min(ans, dis[t][0] + dis[t][1]); dijktra2(t); ans = min(ans, dis[s][0] + dis[s][1]); cout << ans; }

컴파일 시 표준 에러 (stderr) 메시지

commuter_pass.cpp: In function 'void dijktra2(int)':
commuter_pass.cpp:38:30: warning: unused variable 'pa' [-Wunused-variable]
   38 |         int vt = q.top().se, pa = q.top().se; ll kc = q.top().fi; q.pop();
      |                              ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...