제출 #676406

#제출 시각아이디문제언어결과실행 시간메모리
676406borisAngelovCommuter Pass (JOI18_commuter_pass)C++11
100 / 100
357 ms26612 KiB
#include <iostream> #include <algorithm> #include <vector> #include <queue> #include <tuple> using namespace std; const int maxn = 100005; const long long inf = (1LL << 62); vector<pair<long long, long long>> g[maxn]; long long du[maxn]; long long dv[maxn]; long long ds[maxn]; long long dp[2][maxn]; long long ans = 0; bool visited[maxn]; void dijkstra1(long long start_node, long long dist[]) { fill(dist, dist + maxn, inf); priority_queue<pair<long long, long long>> pq; pq.push({0, start_node}); dist[start_node] = 0; while (!pq.empty()) { long long curr = -pq.top().first; long long node = pq.top().second; pq.pop(); if (dist[node] < curr) continue; for (auto [v, w] : g[node]) { long long path = curr + w; if (dist[v] > path) { dist[v] = path; pq.push({-path, v}); } } } } void dijkstra2(long long beg_node, long long end_node) { fill(dp[0], dp[0] + maxn, inf); fill(dp[1], dp[1] + maxn, inf); fill(visited, visited + maxn, 0); priority_queue<pair<long long, pair<long long, long long>>> pq; pq.push({0, {beg_node, 0}}); dp[0][0] = dp[1][0] = inf; while (!pq.empty()) { long long curr = -pq.top().first; long long node = pq.top().second.first; long long par = pq.top().second.second; pq.pop(); if (!visited[node]) { visited[node] = true; ds[node] = curr; dp[0][node] = min(du[node], dp[0][par]); dp[1][node] = min(dv[node], dp[1][par]); for (auto [v, w] : g[node]) { if (!visited[v]) { pq.push({-curr - w, {v, node}}); } } } else if (curr == ds[node]) { if (min(du[node], dp[0][par]) + min(dv[node], dp[1][par]) <= dp[0][node] + dp[1][node]) { dp[0][node] = min(du[node], dp[0][par]); dp[1][node] = min(dv[node], dp[1][par]); } } } ans = min(ans, dp[0][end_node] + dp[1][end_node]); } void fastIO() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); } int main() { fastIO(); long long n, m, s, t, u, v; cin >> n >> m >> s >> t >> u >> v; for (int i = 1; i <= m; ++i) { long long x, y, w; cin >> x >> y >> w; g[x].push_back({y, w}); g[y].push_back({x, w}); } dijkstra1(u, du); dijkstra1(v, dv); ans = du[v]; dijkstra2(s, t); dijkstra2(t, s); cout << ans << endl; return 0; }

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

commuter_pass.cpp: In function 'void dijkstra1(long long int, long long int*)':
commuter_pass.cpp:40:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   40 |         for (auto [v, w] : g[node])
      |                   ^
commuter_pass.cpp: In function 'void dijkstra2(long long int, long long int)':
commuter_pass.cpp:80:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   80 |             for (auto [v, w] : g[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...