제출 #1036880

#제출 시각아이디문제언어결과실행 시간메모리
1036880vaneaCommuter Pass (JOI18_commuter_pass)C++14
100 / 100
196 ms26656 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const int mxN = 1e5+10; vector<array<ll, 2>> adj[mxN]; ll dv[mxN], du[mxN], ans, dp[mxN][2], ds[mxN]; bool vis[mxN]; void dijkstra(int node, ll arr[]) { memset(vis, false, sizeof vis); priority_queue<array<ll, 2>, vector<array<ll, 2>>, greater<array<ll, 2>>> q; q.push({0, node}); while(!q.empty()) { ll dist = q.top()[0], node = q.top()[1]; q.pop(); if(!vis[node]) { vis[node] = true; arr[node] = dist; for(auto [it, w] : adj[node]) { if(!vis[it]) { q.push({dist+w, it}); } } } } } void dijkstra2(int node, int fin) { memset(vis, false, sizeof vis); memset(dp, 0x3F, sizeof dp); priority_queue<array<ll, 3>, vector<array<ll, 3>>, greater<array<ll, 3>>> q; q.push({0, node, 0}); while(!q.empty()) { ll dist = q.top()[0], node = q.top()[1], p = q.top()[2]; q.pop(); if(!vis[node]) { vis[node] = true; ds[node] = dist; dp[node][0] = min(dp[p][0], du[node]); dp[node][1] = min(dp[p][1], dv[node]); for(auto [it, w] : adj[node]) { if(!vis[it]) { q.push({dist+w, it, node}); } } } else { if(dist != ds[node]) continue; ll f = min(dp[p][0], du[node]), s = min(dp[p][1], dv[node]); if(f + s < dp[node][0] + dp[node][1]) { dp[node][0] = f; dp[node][1] = s; } } } ans = min(ans, dp[fin][0] + dp[fin][1]); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, m, s, t, u, v; cin >> n >> m >> s >> t >> u >> v; while(m--) { ll a, b, c; cin >> a >> b >> c; adj[a].push_back({b, c}); adj[b].push_back({a, c}); } dijkstra(u, du); dijkstra(v, dv); ans = du[v]; dijkstra2(s, t); cout << ans; return 0; }

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

commuter_pass.cpp: In function 'void dijkstra(int, ll*)':
commuter_pass.cpp:21:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   21 |             for(auto [it, w] : adj[node]) {
      |                      ^
commuter_pass.cpp: In function 'void dijkstra2(int, int)':
commuter_pass.cpp:43:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   43 |             for(auto [it, w] : adj[node]) {
      |                      ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...