隣接行列の出力 C編（paizaランク B 相当）

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

問題

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

この問題集では、最短経路問題を解くアルゴリズムの一つであるワーシャルフロイド法を扱います。最短経路問題とは、重み付きグラフの与えられた 2 点を結ぶ経路のうち、コスト（距離など）が最小のものを求める問題です。ワーシャルフロイド法を使うと、グラフのすべての 2 点間の最短距離を求めることができます。この問題集では、いくつかのステップにわけてワーシャルフロイド法の理解を深めます。

まずは、与えられるグラフを隣接行列に変換してみましょう。

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

M 本の重み付き有向枝が与えられます。このとき、次のように定義される隣接行列を出力してください。

N × N の正方行列で、上から i 行目、左から j 列目 (1 ≦ i,j ≦ N) の要素が

 i ≠ j のとき
・頂点 i から頂点 j に向かって枝が伸びていればその重み（距離）、そうでなければ 999

i = j のとき
・0

入力される値

N M
a_1 b_1 c_1
...
a_M b_M c_M

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

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

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

期待する出力: 合計 N 行出力してください。i (1 ≦ i ≦ N) 行目には、隣接行列の上から i 行目の N 個の整数を左から順に半角スペース区切りで出力してください。

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

条件

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

入力はすべて整数

2 ≦ N ≦ 100

1 ≦ M ≦ N × (N - 1)

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: 3 2
1 2 5
2 3 1

出力例1: 0 5 999
999 0 1
999 999 0

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

出力例2: 0 4 9 999 999
999 0 999 1 999
999 999 0 999 999
999 999 999 0 3
999 3 999 999 0

問題一覧へ戻る