コスト最小の隣接頂点を探す Python2編（paizaランク C 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
シェア用URL:
ツイートする
問題
下記の問題をプログラミングしてみよう！
連結成分 1、頂点数 N、重み付き、自己ループなしの無向グラフ G が隣接行列の形で与えられます。
G の各頂点 i からのコストが最小で訪問できる頂点を A_i とします。（i ≠ A_i）
A_i のインデックス、i - A_i 間の辺の重みを出力してください。
A_i が複数ある場合、インデックスが最も小さい A_i のインデックスを出力してください。
- 入力される値
-
G の頂点数 N と、 G の隣接行列 C_{i,j} (1 ≦ i, j ≦ N) が与えられます。
C_{i,j} は頂点 i - j の間の辺の重みであり、i - j 間に辺が存在しない場合は 0 が与えられます。
N
C_{1,1} C_{1,2} ... C_{1,N}
C_{2,1} C_{2,2} ... C_{2,N}
...
C_{N,1} C_{N,2} ... C_{N,N}
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
各頂点 i について合計 N 行で以下の出力をしてください。
- 頂点 i からのコストが最小で訪問できる 頂点 A_i と、i - A_i 間の辺の重み C_{i, A_i} を半角スペース区切りで出力してください。
- A_i が複数ある場合、インデックスが最も小さい A_i のインデックスを出力してください。
また、末尾に改行を入れ、余計な文字、空行を含んではいけません。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・ 2 ≦ N ≦ 100
・ 1 ≦ i, j ≦ N
・ 1 ≦ C_{i,j} ≦ 100、または C_{i,j} = 0
- 入力例1
-
3
0 2 0
2 0 1
0 1 0
- 出力例1
-
2 2
3 1
2 1
- 入力例2
-
10
0 6 3 5 9 2 0 0 3 0
6 0 5 7 4 4 6 8 2 0
3 5 0 6 6 7 5 7 9 5
5 7 6 0 5 1 0 0 5 2
9 4 6 5 0 2 0 4 1 1
2 4 7 1 2 0 8 7 3 1
0 6 5 0 0 8 0 0 0 9
0 8 7 0 4 7 0 0 0 7
3 2 9 5 1 3 0 0 0 5
0 0 5 2 1 1 9 7 5 0
- 出力例2
-
6 2
9 2
1 3
6 1
9 1
4 1
3 5
5 4
5 1
5 1
