C++の練習を兼ねて, 競プロ典型 90 問 の 問題013 (Passing) を解いてみた.
■感想.
1. 問題013は, ダイクストラ法を使う方針で, 何とかAC版に到達出来た.
2. ダイクストラ法の復習が出来たので, 非常に良かったと思う.
3. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.
詳細は, 本家のサイト(GitHub) 競プロ典型 90 問 の 問題013 を ご覧下さい.
■C++版プログラム(問題013/AC版).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; #define repex(i, a, b, c) for(int i = a; i < b; i += c) #define repx(i, a, b) repex(i, a, b, 1) #define rep(i, n) repx(i, 0, n) #define repr(i, a, b) for(int i = a; i >= b; i--) #define pb push_back const LL INF = 202020202020202020; const int MAX = 101010; struct edge{ int t; // 次の頂点. LL c; // 所要時間. bool operator < (const edge &E) const { return c > E.c; } }; vector<edge> G[MAX]; int main(){ // 1. 入力情報. int N, M; scanf("%d %d", &N, &M); rep(i, M){ int a, b; LL c; scanf("%d %d %lld", &a, &b, &c); a--; b--; edge e1; e1.t = b; e1.c = c; G[a].pb(e1); edge e2; e2.t = a; e2.c = c; G[b].pb(e2); } // 2. 出発地点から, 目的地点までの最短時間を求める(ダイクストラ法). // https://ja.wikipedia.org/wiki/ダイクストラ法 LL d1[N], d2[N]; rep(i, N) d1[i] = d2[i] = INF; auto dijkstra = [&](int s, LL* d){ // 2-1. 空のキュー. priority_queue<edge> pq; // 2-2. 始点設定. d[s] = 0; pq.push({s, 0}); // 2-3. キュー pq が 空になるまで, 探索. while(!pq.empty()){ // 2-4. 探索を継続するために, 頂点を取得. int u = pq.top().t; LL c = pq.top().c; pq.pop(); // 2-5. より小さい距離が設定済みなら, Skip. if(d[u] < c) continue; // 2-6. 各隣接する頂点について, 所要時間を確認し, 最短時間を更新. rep(i, G[u].size()){ // 最短時間更新. int nu = G[u][i].t; LL nc = c + G[u][i].c; if(d[nu] > nc) d[nu] = nc, pq.push({nu, nc}); } } return; }; // 3. 街 1 -> 街 1 ~ N. dijkstra(0, d1); // 4. 街 N -> 街 1 ~ N. dijkstra(N - 1, d2); // 5. 出力. rep(i, N) printf("%lld\n", d1[i] + d2[i]); return 0; } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 |
[入力例] 7 9 1 2 2 1 3 3 2 5 2 3 4 1 3 5 4 4 7 5 5 6 1 5 7 6 6 7 3 [出力例] 8 8 9 9 8 8 8 ※AtCoderテストケースより [入力例] 4 3 1 2 1 2 3 10 3 4 100 [出力例] 111 111 111 111 ※AtCoderテストケースより [入力例] 4 3 1 2 314 1 3 159 1 4 265 [出力例] 265 893 583 265 ※AtCoderテストケースより [入力例] 12 17 1 2 2 1 3 5 2 5 3 2 4 8 2 9 5 3 8 4 3 9 1 8 9 6 8 10 1 10 11 2 8 11 2 9 12 7 12 4 1 5 4 7 5 6 7 5 7 10 6 7 4 [出力例] 11 11 13 11 13 27 33 21 13 23 25 11 |
■参照サイト
013 – Passing