重みあり有向グラフの隣接行列と隣接リスト JavaScript編（paizaランク B 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
下記の問題をプログラミングしてみよう！
以下の図のような、ノード（頂点）と向きと重みを持つエッジ（辺）の集合を有向グラフといいます。
頂点の数が N であるような有向グラフにおいて、N × N の配列 g を考えます。
i 番目の頂点から j 番目の頂点に向かう重み k の辺があるとき、 g[i - 1][j - 1] = k, 辺がないとき、 g[i - 1][j - 1] = 0
であるような配列をそのグラフの隣接行列といいます。
頂点の数が N であるような有向グラフにおいて、 N 個の配列を持つ２次元配列 g を考えます。
i 番目の頂点から j 番目の頂点に向かう重み k の辺があるとき、 g の i - 1 番目の配列に構造体などを用いて j - 1 と k を追加します。
この操作を繰り返してできる 2 次元配列 g を隣接リストといいます。
グラフの頂点・辺についての情報が与えられるので、このグラフの隣接行列と隣接リストを出力してください。
なお、このグラフには、多重辺や自己ループはないものとします。
- 入力される値
-
N M
a_1 b_1 k_1
...
a_M b_M k_M
・ 1 行目には、頂点の数 N と、辺の数 M が与えられます。
・ 続く M 行では、各辺の両端の頂点 a_i , b_i と、その辺の重み k_i が与えられます。(1 ≦ i ≦ M)
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
2×N 行の出力
・ まず、隣接行列 g を N 行で出力してください。
・ 次に、隣接リスト h を N 行で出力してください。
・ 隣接リストは以下の形式で出力してください。
・ 各行の頂点番号は昇順にソートして出力
・ 頂点 i (1 ≦ i ≦ N) から頂点 j (1 ≦ j ≦ N, j ≠ i) に向かう辺の重みが m_ij のとき、i(m_ij)の形式で出力
・ 頂点 i に隣接している頂点がない場合は改行のみ出力g[0][0]...g[0][N-1]
...
g[N-1][0]...g[N-1][N-1]
h[0][0](m_0h[0][0])h[0][1](m_0h[0][1])...
...
h[N-1][0](m_(N-1)h[N-1][0])h[N-1][1](m_(N-1)h[N-1][1])...
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・ 1 ≦ N ≦ 100
・ 1 ≦ M ≦ N × (N-1) / 2
・ 1 ≦ a_i , b_i ≦ N
・ 1 ≦ k_i ≦ 10000
- 入力例1
-
10 2
5 9 8070
9 10 2464
- 出力例1
-
0000000000
0000000000
0000000000
0000000000
0000000080700
0000000000
0000000000
0000000000
0000000002464
0000000000
8(8070)
9(2464)
- 入力例2
-
20 17
11 4 3748
11 17 1346
12 17 9833
6 12 7794
9 7 6672
13 6 7348
17 13 8287
6 9 5055
11 1 7422
19 3 7471
12 14 9239
2 10 1792
3 12 7928
19 17 6249
14 13 7833
1 8 2173
20 6 6165
- 出力例2
-
00000002173000000000000
00000000017920000000000
00000000000792800000000
00000000000000000000
00000000000000000000
00000000505500779400000000
00000000000000000000
00000000000000000000
00000066720000000000000
00000000000000000000
74220037480000000000001346000
00000000000009239009833000
00000734800000000000000
00000000000078330000000
00000000000000000000
00000000000000000000
00000000000082870000000
00000000000000000000
00747100000000000006249000
00000616500000000000000
7(2173)
9(1792)
11(7928)
8(5055)11(7794)
6(6672)
0(7422)3(3748)16(1346)
13(9239)16(9833)
5(7348)
12(7833)
12(8287)
2(7471)16(6249)
5(6165)
