C++の練習を兼ねて, AtCoder Beginner Contest 051 の 問題D (D – Candidates of No Shortest Paths) を解いてみた.
■感想.
1. バグに気付くまでに時間かかってしまった(※M辺 の 入力情報を, N辺 に 誤記していた, debug中に, 漸く気付いた).
2. ほとんど馴染みのないダイクストラ法の訓練を出来たので良かったと思う.
3. 解説を見る前に, 何とか解答出来たので, とりあえず良かったと思う.
本家のサイトABC 051解説をご覧下さい.
■C++版プログラム(問題D/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 |
#include <bits/stdc++.h> using namespace std; const int INF = 1e8; int N, M; struct edge { int to; // 次の頂点. int d; // 距離. bool operator < (const edge &E) const { return d > E.d; } }; int dist[101][101]; // 頂点(i, j) の 最短距離 を 保存. vector<edge> graph[1001]; // https://ja.wikipedia.org/wiki/ダイクストラ法 // グラフを最良優先探索する. // ※dijkstraの動作確認用. // @param s: 今回探索する頂点番号. // @return: 特に無し. void dijkstra(int s) { // 1. 初期化. priority_queue<edge> pq; // 2. 始点設定. dist[s][s] = 0; pq.push({s, 0}); // 3. キュー pq が 空になるまで, 探索. while(!pq.empty()){ // 4. 探索を継続するために, 頂点を取得. int u = pq.top().to; int d = pq.top().d; pq.pop(); // 5. より小さい距離が設定済みなら, Skip. if(dist[s][u] < d) continue; // 6. 各隣接する頂点について, 距離を確認し, 最短経路を更新. for(int i = 0; i < graph[u].size(); ++i){ int nu = graph[u][i].to; int nd = d + graph[u][i].d; // 最短経路更新. if(dist[s][nu] > nd) dist[s][nu] = nd, pq.push({nu, nd}); } } } int main() { // 1. 入力情報取得. scanf("%d %d", &N, &M); map<pair<int, int>, int> m; // 二頂点間の距離を保存. for(int i = 0; i < M; i++){ int a, b, c; scanf("%d %d %d", &a, &b, &c); a--, b--; if(a > b) swap(a, b); graph[a].push_back({b, c}); graph[b].push_back({a, c}); m[{a, b}] = c; } // 2. 各二頂点間の最短経路を求める(ダイクストラ法). int ans = 0; for(int i = 0; i < 101; i++) for(int j = 0; j < 101; j++) dist[i][j] = INF; for(int i = 0; i < N - 1; i++){ dijkstra(i); for(int j = i + 1; j < N; j++){ // 始めに保存した二頂点間の距離が, 最短経路探索後の二頂点間の距離と異なっているのであれば, // この辺は, 最短経路に含まれてないと判定. if(m[{i, j}] > 0 && m[{i, j}] != dist[i][j]) ans++; // printf("m[{%d, %d}]=%d dist[%d][%d]=%d\n", i, j, m[{i, j}], i, j, dist[i][j]); } } // 3. 出力 ~ 後処理. printf("%d\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 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 |
[入力例] 3 3 1 2 1 1 3 1 2 3 3 [出力例(debug版)] m[{0, 1}]=1 dist[0][1]=1 m[{0, 2}]=1 dist[0][2]=1 m[{1, 2}]=3 dist[1][2]=2 1 ※AtCoderテストケースより [入力例] 3 2 1 2 1 2 3 1 [出力例(debug版)] m[{0, 1}]=1 dist[0][1]=1 m[{0, 2}]=0 dist[0][2]=2 m[{1, 2}]=1 dist[1][2]=1 0 ※AtCoderテストケースより [入力例] 4 4 1 2 5 2 3 3 4 1 2 3 4 1 [出力例(debug版)] m[{0, 1}]=5 dist[0][1]=5 m[{0, 2}]=0 dist[0][2]=3 m[{0, 3}]=2 dist[0][3]=2 m[{1, 2}]=3 dist[1][2]=3 m[{1, 3}]=0 dist[1][3]=4 m[{2, 3}]=1 dist[2][3]=1 0 [入力例] 12 14 1 2 2 8 2 1 8 9 3 2 3 2 9 3 12 3 4 1 3 6 5 5 6 15 6 7 6 4 10 2 10 12 1 4 5 10 12 5 1 5 11 1 [出力例(debug版)] m[{0, 1}]=2 dist[0][1]=2 m[{0, 2}]=0 dist[0][2]=4 m[{0, 3}]=0 dist[0][3]=5 m[{0, 4}]=0 dist[0][4]=9 m[{0, 5}]=0 dist[0][5]=9 m[{0, 6}]=0 dist[0][6]=15 m[{0, 7}]=0 dist[0][7]=3 m[{0, 8}]=0 dist[0][8]=6 m[{0, 9}]=0 dist[0][9]=7 m[{0, 10}]=0 dist[0][10]=10 m[{0, 11}]=0 dist[0][11]=8 m[{1, 2}]=2 dist[1][2]=2 m[{1, 3}]=0 dist[1][3]=3 m[{1, 4}]=0 dist[1][4]=7 m[{1, 5}]=0 dist[1][5]=7 m[{1, 6}]=0 dist[1][6]=13 m[{1, 7}]=1 dist[1][7]=1 m[{1, 8}]=0 dist[1][8]=4 m[{1, 9}]=0 dist[1][9]=5 m[{1, 10}]=0 dist[1][10]=8 m[{1, 11}]=0 dist[1][11]=6 m[{2, 3}]=1 dist[2][3]=1 m[{2, 4}]=0 dist[2][4]=5 m[{2, 5}]=5 dist[2][5]=5 m[{2, 6}]=0 dist[2][6]=11 m[{2, 7}]=0 dist[2][7]=3 m[{2, 8}]=12 dist[2][8]=6 m[{2, 9}]=0 dist[2][9]=3 m[{2, 10}]=0 dist[2][10]=6 m[{2, 11}]=0 dist[2][11]=4 m[{3, 4}]=10 dist[3][4]=4 m[{3, 5}]=0 dist[3][5]=6 m[{3, 6}]=0 dist[3][6]=12 m[{3, 7}]=0 dist[3][7]=4 m[{3, 8}]=0 dist[3][8]=7 m[{3, 9}]=2 dist[3][9]=2 m[{3, 10}]=0 dist[3][10]=5 m[{3, 11}]=0 dist[3][11]=3 m[{4, 5}]=15 dist[4][5]=10 m[{4, 6}]=0 dist[4][6]=16 m[{4, 7}]=0 dist[4][7]=8 m[{4, 8}]=0 dist[4][8]=11 m[{4, 9}]=0 dist[4][9]=2 m[{4, 10}]=1 dist[4][10]=1 m[{4, 11}]=1 dist[4][11]=1 m[{5, 6}]=6 dist[5][6]=6 m[{5, 7}]=0 dist[5][7]=8 m[{5, 8}]=0 dist[5][8]=11 m[{5, 9}]=0 dist[5][9]=8 m[{5, 10}]=0 dist[5][10]=11 m[{5, 11}]=0 dist[5][11]=9 m[{6, 7}]=0 dist[6][7]=14 m[{6, 8}]=0 dist[6][8]=17 m[{6, 9}]=0 dist[6][9]=14 m[{6, 10}]=0 dist[6][10]=17 m[{6, 11}]=0 dist[6][11]=15 m[{7, 8}]=3 dist[7][8]=3 m[{7, 9}]=0 dist[7][9]=6 m[{7, 10}]=0 dist[7][10]=9 m[{7, 11}]=0 dist[7][11]=7 m[{8, 9}]=0 dist[8][9]=9 m[{8, 10}]=0 dist[8][10]=12 m[{8, 11}]=0 dist[8][11]=10 m[{9, 10}]=0 dist[9][10]=3 m[{9, 11}]=1 dist[9][11]=1 m[{10, 11}]=0 dist[10][11]=2 3 [入力例(subtask_1_16.txt)] 12 66 1 2 410 1 3 546 1 4 980 1 5 360 1 6 878 1 7 134 1 8 126 1 9 463 1 10 699 1 11 822 1 12 743 2 3 879 2 4 558 2 5 893 2 6 206 2 7 909 2 8 544 2 9 730 2 10 575 2 11 200 2 12 598 3 4 221 3 5 864 3 6 245 3 7 618 3 8 894 3 9 396 3 10 749 3 11 185 3 12 655 4 5 787 4 6 90 4 7 715 4 8 61 4 9 664 4 10 941 4 11 870 4 12 74 5 6 593 5 7 747 5 8 611 5 9 30 5 10 547 5 11 219 5 12 64 6 7 138 6 8 804 6 9 905 6 10 356 6 11 163 6 12 439 7 8 727 7 9 973 7 10 589 7 11 739 7 12 511 8 9 493 8 10 717 8 11 444 8 12 98 9 10 753 9 11 670 9 12 849 10 11 436 10 12 585 11 12 949 [出力例(debug版)] m[{0, 1}]=410 dist[0][1]=410 m[{0, 2}]=546 dist[0][2]=408 m[{0, 3}]=980 dist[0][3]=187 m[{0, 4}]=360 dist[0][4]=288 m[{0, 5}]=878 dist[0][5]=272 m[{0, 6}]=134 dist[0][6]=134 m[{0, 7}]=126 dist[0][7]=126 m[{0, 8}]=463 dist[0][8]=318 m[{0, 9}]=699 dist[0][9]=628 m[{0, 10}]=822 dist[0][10]=435 m[{0, 11}]=743 dist[0][11]=224 m[{1, 2}]=879 dist[1][2]=385 m[{1, 3}]=558 dist[1][3]=296 m[{1, 4}]=893 dist[1][4]=419 m[{1, 5}]=206 dist[1][5]=206 m[{1, 6}]=909 dist[1][6]=344 m[{1, 7}]=544 dist[1][7]=357 m[{1, 8}]=730 dist[1][8]=449 m[{1, 9}]=575 dist[1][9]=562 m[{1, 10}]=200 dist[1][10]=200 m[{1, 11}]=598 dist[1][11]=370 m[{2, 3}]=221 dist[2][3]=221 m[{2, 4}]=864 dist[2][4]=359 m[{2, 5}]=245 dist[2][5]=245 m[{2, 6}]=618 dist[2][6]=383 m[{2, 7}]=894 dist[2][7]=282 m[{2, 8}]=396 dist[2][8]=389 m[{2, 9}]=749 dist[2][9]=601 m[{2, 10}]=185 dist[2][10]=185 m[{2, 11}]=655 dist[2][11]=295 m[{3, 4}]=787 dist[3][4]=138 m[{3, 5}]=90 dist[3][5]=90 m[{3, 6}]=715 dist[3][6]=228 m[{3, 7}]=61 dist[3][7]=61 m[{3, 8}]=664 dist[3][8]=168 m[{3, 9}]=941 dist[3][9]=446 m[{3, 10}]=870 dist[3][10]=253 m[{3, 11}]=74 dist[3][11]=74 m[{4, 5}]=593 dist[4][5]=228 m[{4, 6}]=747 dist[4][6]=366 m[{4, 7}]=611 dist[4][7]=162 m[{4, 8}]=30 dist[4][8]=30 m[{4, 9}]=547 dist[4][9]=547 m[{4, 10}]=219 dist[4][10]=219 m[{4, 11}]=64 dist[4][11]=64 m[{5, 6}]=138 dist[5][6]=138 m[{5, 7}]=804 dist[5][7]=151 m[{5, 8}]=905 dist[5][8]=258 m[{5, 9}]=356 dist[5][9]=356 m[{5, 10}]=163 dist[5][10]=163 m[{5, 11}]=439 dist[5][11]=164 m[{6, 7}]=727 dist[6][7]=260 m[{6, 8}]=973 dist[6][8]=396 m[{6, 9}]=589 dist[6][9]=494 m[{6, 10}]=739 dist[6][10]=301 m[{6, 11}]=511 dist[6][11]=302 m[{7, 8}]=493 dist[7][8]=192 m[{7, 9}]=717 dist[7][9]=507 m[{7, 10}]=444 dist[7][10]=314 m[{7, 11}]=98 dist[7][11]=98 m[{8, 9}]=753 dist[8][9]=577 m[{8, 10}]=670 dist[8][10]=249 m[{8, 11}]=849 dist[8][11]=94 m[{9, 10}]=436 dist[9][10]=436 m[{9, 11}]=585 dist[9][11]=520 m[{10, 11}]=949 dist[10][11]=283 46 ※AtCoderテストケースより |
■参照サイト
AtCoder Beginner Contest 051
atcoder_testcases ABC051