C++の練習を兼ねて, AtCoder Beginner Contest 012 の 問題D (D – バスと避けられない運命) を解いてみた.
■感想.
1. ワーシャル–フロイド法 の 復習が出来たので, 良かったと思う.
2. 解答を見る前に, 解けたので, 及第点は取れたと思う.
本家のサイトAtCoder Beginner Contest 012 解説をご覧下さい.
■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 |
#include <bits/stdc++.h> using namespace std; const int MAX = 301; const int INF = 123454321; int rideTime[MAX][MAX]; int rideMaxTime[MAX]; int main(){ // 1. 入力情報取得. int N, M; scanf("%d %d", &N, &M); for(int i = 0; i < MAX; i++) for(int j = 0; j < MAX; j++) if(i != j) rideTime[i][j] = INF; for(int i = 0; i < M; i++){ int a, b, t; scanf("%d %d %d", &a, &b, &t); rideTime[a][b] = t; rideTime[b][a] = t; } // 2. ワーシャル–フロイド法. for(int k = 1; k <= N; k++){ for(int i = 1; i <= N; i++){ for(int j = 1; j <= N; j++){ rideTime[i][j] = min(rideTime[i][j], rideTime[i][k] + rideTime[k][j]); } } } // 3. 各バス停を出発地点と仮定した場合の最大の乗車時間を確認. for(int i = 1; i <= N; i++) for(int j = 1; j <= N; j++) rideMaxTime[i] = max(rideMaxTime[i], rideTime[i][j]); // 4. 引っ越し先を決めて, 最大の乗車時間を確認. int ans = INF; for(int i = 1; i <= N; i++) ans = min(ans, rideMaxTime[i]); // 5. 出力 ～ 後処理. 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 |
[入力例] 3 2 1 2 10 2 3 10 [出力例] 10 ※AtCoderテストケースより [入力例] 5 5 1 2 12 2 3 14 3 4 7 4 5 9 5 1 18 [出力例] 26 ※AtCoderテストケースより [入力例] 4 6 1 2 1 2 3 1 3 4 1 4 1 1 1 3 1 4 2 1 [出力例] 1 ※AtCoderテストケースより [入力例] 5 4 1 2 7 3 2 13 3 4 11 5 4 9 [出力例] 20 [入力例] 5 7 1 2 10 3 2 7 3 1 12 5 1 15 1 4 8 3 4 5 5 4 3 [出力例] 12 |
■参照サイト
AtCoder Beginner Contest 012