ワーシャルフロイド法の実装 Python2編（paizaランク A 相当）

問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！

問題

下記の問題をプログラミングしてみよう！

1, ..., N の番号がついた N 個の頂点とそれらをつなぐ枝からなる有向グラフを考えます。ただし、自己ループと多重辺は考えません。

M 本の重み付き有向枝が与えられます。その後、Q 個の頂点の組 (d,e) が与えられます。各組について、頂点 d を出発し、頂点 e へ向かう経路の最短距離を出力してください。

なお、各頂点間の最短距離はワーシャルフロイド法を利用して求めてください。
ワーシャルフロイド法は、

3 つの頂点 (始点、経由点、終点) を選んで、(始点 → 経由点 → 終点) の最短距離が
現在の (始点 → 終点) の最短距離より短ければ、その距離を新たに (始点 → 終点) の最短距離とする

という操作を、すべての組み合わせについておこなうアルゴリズムです。

ただし、経路（枝の集合）の距離とはその経路を構成する枝の重みの和とします。ある頂点からその頂点自身へ移動する場合は、その区間の重みを 0 とします。また経路が存在しない場合は、その距離を 999 としてください。

ヒント

各頂点間の距離を保持するには、二次元配列を使いましょう。そしてその初期値は、前問で扱った隣接行列とすると良いでしょう。

3 つの頂点のすべての組み合わせを調べればいいため、3 つのループでの実装が可能です。

どの順番で頂点の組み合わせを調べるかが重要です。

入力される値

N M Q
a_1 b_1 c_1
...
a_M b_M c_M
d_1 e_1
...
d_Q e_Q

1 行目に、頂点の個数を表す整数 N と、枝の本数を表す整数 M と、頂点の組の数を表す整数 Q が与えられます。

i + 1 行目に枝 i を表す整数の組 (a_i, b_i, c_i) が与えられます。枝 i は、頂点 a_i から頂点 b_i に向かう枝で、その重み（距離）は c_i です。(1 ≦ i ≦ M)

j + M + 1 行目に、頂点の組 (d_j, e_j) が与えられます。(1 ≦ j ≦ Q)

入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。標準入力からの値取得方法はこちらをご確認ください

期待する出力: 合計 Q 行出力してください。i (1 ≦ j ≦ Q) 行目には、始点 d_j から終点 e_j までの最短距離を出力してください。

また末尾に改行を入れ、余計な文字、空行を含んではいけません。

条件

すべてのテストケースにおいて、以下の条件をみたします。

入力はすべて整数

2 ≦ N ≦ 100

1 ≦ M ≦ N × (N - 1)

1 ≦ Q ≦ 100

1 ≦ a_i, b_i ≦ N (1 ≦ i ≦ M)

a_i ≠ b_i (1 ≦ i ≦ M)

1 ≦ c_i ≦ 10 (1 ≦ i ≦ M)

同じ頂点の組（順序組）は 2 回以上入力されない

1 ≦ d_j, e_j ≦ N (1 ≦ j ≦ Q)

入力例1: 3 6 3
1 2 10
2 1 1
1 3 2
3 1 3
2 3 4
3 2 1
1 2
3 2
3 1

出力例1: 3
1
2

入力例2: 5 7 5
1 2 4
1 3 9
2 4 1
4 5 3
5 2 3
3 4 2
1 4 6
2 1
5 4
3 5
1 2
3 2

出力例2: 999
4
5
4
8

入力例3: 5 4 1
1 3 1
3 5 1
5 4 1
4 2 1
1 2

出力例3: 4

問題一覧へ戻る