ひとりで勝手にはじめた蟻本読書会 グラフ理論 いわゆる牛ゲーと最短路問題とベルマンフォード法 蟻本読書会 の続きです。
ワーシャルフロイド法と全ペアの最短経路
ワーシャルフロイド法は、重み付き有向グラフの全ペアの最短経路問題を多項式時間で解くアルゴリズムです。考案者がスティーブン・ワーシャルとロバート・フロイドであったことからこのような名前で呼ばれています。
実装が非常に簡単です。まず2次元配列を定義し、dp[i, j] には頂点 i から頂点 j までの距離をセットします。dp[i, i] は自分自身への距離なので 0 、頂点 i から頂点 j までの辺が存在しない場合は dp[i, j] には ∞ をセットします
i から j まで移動するときの最小コストを計算するさいに頂点 k を経由したほうがコストが低くなる場合があります。そこでこれを計算します。
|
1 2 3 4 5 6 7 8 |
for (int k = 0; k < N; k++) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) dp[i, j] = Math.Min(dp[i, j], dp[i, k] + dp[k, j]); } } |
計算量は O(N ^ 3) でありダイクストラ法やベルマンフォード法と比べると遅いです。ただ頂点の全ペアの最短経路を知りたいときには便利です。
ワーシャルフロイド法は、負のコストの辺がある場合でも解くことができます。例えば、 dp[i, i]) が負となるような i が存在すればこのグラフは負の閉路を含みます。
基本問題
1, … , N の番号がついた N 個の頂点とそれらをつなぐ枝からなる有向グラフを考えます。ただし、自己ループと多重辺は考えません。
M 本の重み付き有向枝が与えられます。その後、Q 個の頂点の組 (d,e) が与えられます。各組について、頂点 d を出発し、頂点 e へ向かう経路の最短距離（経路が存在しない場合は 999）を出力してください。
入力されるデータ
N M Q
a_1 b_1 c_1
…
a_M b_M c_M
d_1 e_1
…
d_Q e_Q（ただし
2 ≦ N ≦ 100
1 ≦ M ≦ N × (N – 1)
1 ≦ Q ≦ 100
1 ≦ a_i, b_i ≦ N
1 ≦ c_i ≦ 10
1 ≦ d_j, e_j ≦ N ）
|
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 |
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { int N, M, Q; { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); N = vs[0]; M = vs[1]; Q = vs[2]; } long[,] dp = new long[N, N]; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) dp[i, j] = 999; } for (int i = 0; i < N; i++) dp[i, i] = 0; for (int i = 0; i < M; i++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int a = vs[0] - 1; int b = vs[1] - 1; int c = vs[2]; dp[a, b] = c; } for (int k = 0; k < N; k++) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) dp[i, j] = Math.Min(dp[i, j], dp[i, k] + dp[k, j]); } } List<long> rets = new List<long>(); for (int i = 0; i < Q; i++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int d = vs[0] - 1; int e = vs[1] - 1; rets.Add(dp[d, e]); } foreach (long ret in rets) Console.WriteLine(ret); } } |
応用問題
魔法少女のjoisinoお姉ちゃんは、この世にあるすべての数字を 1 に変えてやろうと思い立ちました。
1 つの数字を i から j(0 ≦ i, j ≦ 9) に書き変えるには魔力 c_i,j が必要です。
今、目の前にある壁は縦方向に H、横方向に W のマス目になっていて、1 つ以上のマス目に 0 以上 9 以下の整数が 1 つずつ書かれています。
上から i(1 ≦ i ≦ H) 番目、左から j(1 ≦ j ≦ W) 番目のマスの情報として A_i,j が与えられ、
A_i,j ≠ -1 の場合はマスに A_i,j が書かれている
A_i,j = -1 の場合はマスに数字が書かれていない
ことを意味します。この壁に書かれている数字を最終的に全て 1 に変えるのに必要な魔力の最小量を求めてください。
H W
c_0,0 c_0,1 … c_0,9
c_1,0 c_1,1 … c_1,9
…
c_9,0 c_9,1 … c_9,9
A_1,1 A_1,2 … A_1,W
A_2,1 A_2,2 … A_2,W
…
A_H,1 A_H,2 … A_H,W（ただし、1 ≦ H, W ≦ 200
1 ≦ c_i,j ≦ 10^3, 1 ≦ A_i,j ≦ 9 ）
ワーシャルフロイド法ですべての整数について 1 に変えるために必要な魔力の最小値を求めます。あとはこれを用いて壁に書かれている数字を1に変えるための魔力の総和を求めるだけです。
|
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 |
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { int H, W; { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); H = vs[0]; W = vs[1]; } long[,] dp = new long[10, 10]; for (int i = 0; i < 10; i++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); for (int j = 0; j < 10; j++) dp[i, j] = vs[j]; } for (int k = 0; k < 10; k++) { for (int i = 0; i < 10; i++) { for (int j = 0; j < 10; j++) dp[i, j] = Math.Min(dp[i, j], dp[i, k] + dp[k, j]); } } long ans = 0; for (int i = 0; i < H; i++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); for (int j = 0; j < W; j++) { if (vs[j] == -1) // -1 は無視 continue; ans += dp[vs[j], 1]; } } Console.WriteLine(ans); } } |
高橋君は、バスがあまり好きではありません。社会人になると、自宅から会社まで、バスで通わなければなりません。高橋君はまだ内定を貰っていないので、会社の場所は解りません。
高橋君は、バスに乗っている時間が最も長くなってしまうような、最悪のケースを常に想定します。 この、最悪なケースのバスに乗っている時間が、出来るだけ短くなるような場所に引っ越そうと思っています。
各バスは、2 つのバス停を往復するように走っており、行き・帰りでかかる時間に差はありません。また、自宅や会社はバス停に隣接しており、他のバス停まで歩いたり、バス以外の手段で移動することはできません。バスの待ち時間、乗継にかかる時間などは無視します。
高橋君が引っ越すべき場所を求め、そこに引っ越した際の、バスに乗らなければならない時間の最大値を出力してください。
入力されるデータ
N M
a_1 b_1 t_1
a_2 b_2 t_2
…
a_M b_M t_M（ただし、N はバス停の数を表す整数 2 ≦ N ≦ 300
M は路線の数を表す整数 1 ≦ M ≦ 44850
1 ≦ a_i b_i ≦ N
1 ≦ c_i ≦ 1000
辿り着けないバス停のペアは存在しないことが保証されている）
ある頂点 K を定め、そこからそれ以外の頂点への距離の最大値を求める、そしてその最大値が最小になる K を求めることができればこの問題は解けます。最初に全ペアの最短経路を求めてしまえばこれをつかって解を求めることができます。ダイクストラ法でも間に合いますが、ここはワーシャルフロイド法で解きましょう。
|
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 |
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { int N, M; { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); N = vs[0]; M = vs[1]; } long[,] dp = new long[N, N]; // 全要素を足したときにオーバーフローしない程度の巨大な値で初期化 for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) dp[i, j] = long.MaxValue / 2; } for (int i = 0; i < N; i++) dp[i, i] = 0; for (int i = 0; i < M; i++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int a = vs[0] - 1; int b = vs[1] - 1; int t = vs[2]; dp[a, b] = t; dp[b, a] = t;// 逆向き移動可なので・・・ } for (int k = 0; k < N; k++) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) dp[i, j] = Math.Min(dp[i, j], dp[i, k] + dp[k, j]); } } long ans = long.MaxValue; for (int i = 0; i < N; i++) { // ある頂点を定め、そこからそれ以外の頂点への距離の最大値を求める long max = 0; for (int j = 0; j < N; j++) max = Math.Max(max, dp[i, j]); // その最大値の最小値は？ ans = Math.Min(ans, max) ; } Console.WriteLine(ans); } } |
Atcoder国には N 個の町があり、M 本の双方向に移動可能な道で結ばれています。また i 本目の道は町 A_i と町 B_i の間を距離 C_i で結んでいます。
joisinoお姉ちゃんは、この国の R 個の町 r_1, r_2, .. , r_R を訪れることとなりました。最初に訪れる町までの移動と、最後に訪れる町からの移動は空路で行うが、それ以外は道を使わなければなりません。
町を訪れる順番を、道での移動距離が最小となるように決めた時の移動距離を答えてください。
入力されるデータ
N M R
r_1 … r_R
A_1 B_1 C_1
A_2 B_2 C_2
…
A_M B_M C_M（ただし、
2 ≦ N ≦ 200, 1 ≦ M ≦ N ×(N – 1) / 2
2 ≦ R ≦ min(8, N)
1≦ C_i ≦ 100,000 ）
これも最初にワーシャルフロイド法で街相互の最短距離を求めておくと速く解を求めることができるかもしれません。街相互の最短距離を求めることができたら { 0, 1, …, R – 1 } の順列を生成して r_1, r_2, .. , r_R の順番を変えて全通り試してみます。この処理で得られた最小値が求める解となります。
{ 0, 1, …, R – 1 } の順列を生成するNextPermutationメソッドは n! 通りの全探索 next_permutation 意外と奥が深い全探索 蟻本読書会 と同じものを使っています。
|
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 |
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { int N, M, R; { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); N = vs[0]; M = vs[1]; R = vs[2]; } int[] r = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); r = r.Select(_ => _ - 1).ToArray(); // 0 ベースのインデックスに変更 long[,] dp = new long[N, N]; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) dp[i, j] = long.MaxValue / 2; } for (int i = 0; i < N; i++) dp[i, i] = 0; for (int i = 0; i < M; i++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int a = vs[0] - 1; int b = vs[1] - 1; int c = vs[2]; dp[a, b] = c; dp[b, a] = c; } for (int k = 0; k < N; k++) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) dp[i, j] = Math.Min(dp[i, j], dp[i, k] + dp[k, j]); } } // { 0, 1, …, R - 1 } の順列を生成 int[] array = new int[R]; for (int i = 0; i < R; i++) array[i] = i; // 全訪問順を試す long ans = long.MaxValue; do { long distance = 0; for (int i = 0; i < R - 1; i++) { int from = r[ array[i]]; int to = r[array[i + 1]]; distance += dp[from, to]; } ans = Math.Min(ans, distance); } while (NextPermutation(array, 0)); Console.WriteLine(ans); } public static bool NextPermutation(int[] array, int start) { int length = array.Length; int end = start + length - 1; if (end <= start) return false; int last = end; while (true) { int pos = last--; if (array[last].CompareTo(array[pos]) < 0) { int i; for (i = end + 1; array[last].CompareTo(array[--i]) >= 0;) { } int tmp = array[last]; array[last] = array[i]; array[i] = tmp; Array.Reverse(array, pos, end - pos + 1); return true; } if (last == start) { Array.Reverse(array, start, end - start); return false; } } throw new Exception("NextPermutation: Fatal error"); } } |
