コスト最小の隣接頂点を探す Ruby編（paizaランク C 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
下記の問題をプログラミングしてみよう！
連結成分 1、頂点数 N、重み付き、自己ループなしの無向グラフ G が隣接行列の形で与えられます。
さらに、ある頂点 v からの各頂点へのコストがランダムな整数で初期化された配列が H で与えられます。
v から各頂点への最小コストを求め、 H の全要素を最小コストに更新して出力してください。
- 入力される値
-
・ G の頂点数 N
・ G の隣接行列 C_{i,j} (1 ≦ i, j ≦ N)
・ ある頂点 v からの頂点 i へのコストがランダムな整数で初期化された H_i (1 ≦ i ≦ N)
・ C_{i,j} は頂点 i - j の間の辺の重みであり、i - j 間に辺が存在しない場合は 0 が与えられます。N v
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}
H_1 H_2 ... H_N
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
H の各要素を N 行で出力をしてください。
また、末尾に改行を入れ、余計な文字、空行を含んではいけません。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・ 2 ≦ N ≦ 100
・ 1 ≦ v ≦ N
・ 1 ≦ i, j ≦ N
・ 1 ≦ C_{i,j} ≦ 100、または C_{i,j} = 0
・ 0 ≦ H_i ≦ 100、または H_i = 0
- 入力例1
-
3 1
0 2 3
2 0 1
3 1 0
0 20 30
- 出力例1
-
0
2
3
- 入力例2
-
10 4
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
5 10 33 0 6 12 2 7 9 10
- 出力例2
-
3
5
6
0
3
1
2
7
4
2
