C++の練習を兼ねて, AtCoder Regular Contest 035 の 問題C (アットコーダー王国の交通事情) を解いてみた.
■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. Warshall–Floyd法の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Regular Contest 035 解説 を ご覧下さい.
■C++版プログラム(問題C／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 |
// 解き直し. // https://www.slideshare.net/chokudai/arc035 // 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--) const LL INF = 202020202020202020; LL d[404][404]; int main(){ // 1. 入力情報. int N, M; scanf("%d %d", &N, &M); rep(i, N) rep(j, N) if(i != j) d[i][j] = INF; rep(i, M){ int a, b, c; scanf("%d %d %d", &a, &b, &c); --a, --b; d[a][b] = c; d[b][a] = c; } // 2. Warshall–Floyd法(※各頂点間の最短距離を保存). rep(k, N) rep(i, N) rep(j, N) d[i][j] = min(d[i][j], d[i][k] + d[k][j]); // 3. クエリ回答. int K; scanf("%d", &K); rep(_, K){ // 3-1. 道路を新たに建設. int x, y, z; scanf("%d %d %d", &x, &y, &z); --x, --y; // 3-2. 最短距離更新. rep(i, N) rep(j, N) d[i][j] = min({d[i][j], d[i][x] + d[y][j] + (LL)z, d[i][y] + d[x][j] + (LL)z}); // 3-3. 幸福度. LL ans = 0; rep(i, N) repx(j, i + 1, N) ans += d[i][j]; printf("%lld\n", ans); } 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 82 83 84 85 86 87 88 89 90 91 92 93 94 |
[入力例] 4 3 1 2 1 2 3 1 3 4 10 2 3 4 1 1 4 1 [出力例] 10 8 ※AtCoderテストケースより [入力例] 8 16 8 7 38 2 8 142 5 2 722 8 6 779 4 6 820 1 3 316 1 7 417 8 3 41 1 4 801 3 2 126 4 2 71 8 4 738 4 3 336 7 5 717 5 6 316 2 1 501 10 6 1 950 6 1 493 1 6 308 3 4 298 2 5 518 1 5 402 4 7 625 7 6 124 3 8 166 2 4 708 [出力例] 13649 12878 11954 11954 11280 11058 11058 8099 8099 8099 ※AtCoderテストケースより [入力例] 10 12 2 1 30 2 8 33 2 10 37 10 8 32 10 9 25 8 9 41 9 3 72 3 4 111 6 4 55 6 7 123 5 6 210 5 1 108 10 5 1 100 5 6 222 5 7 321 4 9 170 8 3 111 5 2 123 2 6 333 8 4 210 5 4 234 8 6 345 [出力例] 8338 8338 8314 8145 8143 8108 8108 8105 8074 8074 |
■参照サイト
AtCoder Regular Contest 035