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