今回は paiza の「重みあり有向グラフの隣接行列と隣接リスト」の問題に挑戦！

問題概要

問題のテーマ

重み付き有向グラフを
- 隣接行列
- 隣接リスト
  の 2つの表現で出力する問題

入力として与えられるもの

N：頂点の数
M：辺の数
各辺について
- a → b：向きのある辺
- k：その辺の重み

グラフの条件

有向グラフ（向きあり）
重みあり
多重辺なし
自己ループなし

出力内容（合計 2N 行）

① 隣接行列（N 行）

サイズ：N × N
意味：
- i → j に重み k の辺がある → g[i-1][j-1] = k
- 辺がない → 0
各行は数値をスペースなしで連結して出力

② 隣接リスト（N 行）

各行は「その頂点から出る辺」を表す
出力ルール：
- 接続先の頂点番号で昇順ソート
- b(k) の形式で横に並べる
- 辺がなければ「空行」

入力例:

10 2
5 9 8070
9 10 2464

出力例:

0000000000
0000000000
0000000000
0000000000
0000000080700
0000000000
0000000000
0000000000
0000000002464
0000000000




8(8070)



9(2464)

✅OK例：

const rl = require('readline').createInterface({ input: process.stdin });

const lines = [];

rl.on('line', line => lines.push(line));

rl.on('close', () => {
    const [N, M] = lines[0].split(' ').map(Number);
    const points = lines.slice(1).map(p => p.split(' ').map(Number));
    
    const gMatrix = Array.from({ length: N }, () => Array(N).fill(0)); // 隣接行列
    const gList = Array.from({ length: N }, () => []); // 隣接リスト
    
    for (let i = 0; i < M; i++) {
        const [a, b, k] = points[i]; // 頂点a→bと重みk
        
        gMatrix[a-1][b-1] = k;
        
        gList[a-1].push([b-1, k]);
    }
    
    gMatrix.forEach(g => console.log(g.join('')));
    
    for (let i = 0; i < N; i++) {
        gList[i].sort((a, b) => a[0] - b[0]); // 頂点番号でソート
        for (const val of gList[i]) {
            const [b, k] = val;
            process.stdout.write(`${b}(${k})`);
        }
        console.log();
    }
});

🔍 コードの流れ

readline を使って標準入力を1行ずつ配列 lines に格納
入力終了後（close）に処理開始
1行目から
- 頂点数 N
- 辺の数 M
  を取得
2行目以降から
- 各辺の情報 [a, b, k]
  を配列 points にまとめて格納
隣接行列 gMatrix
- サイズ N × N
- 初期値はすべて 0
隣接リスト gList
- 長さ N
- 各要素は空配列で初期化
各辺について繰り返し処理
- a → b に重み k の辺を
  - 隣接行列：gMatrix[a-1][b-1] = k
  - 隣接リスト：gList[a-1] に [b-1, k] を追加
隣接行列を各行ごとに連結して出力
各頂点 i について
- 隣接リスト gList[i] を接続先頂点番号で昇順ソート
- b(k) の形式で横に並べて出力
- 接続先がなければ空行を出力

📝まとめ

グラフ表現について

隣接行列
- 全頂点間の関係を一気に見られる
- 実装がシンプル
- サイズは常に N × N
隣接リスト
- 実際に辺がある部分だけを持つ
- 可変長配列が必要

「重みあり」で増えたポイント

辺の情報は
- 「行き先の頂点」
- 「重み」
  をセットで扱う必要がある
隣接リストでは
- [行き先, 重み]
  のような構造で管理するのが基本

実装上の重要ポイント

入力は 1-index
配列は 0-index
→ 内部処理では -1 して扱う
出力は問題の仕様・例に完全に従う
隣接リストは頂点でソートしてから出力する必要がある