Error in user YAML: (<unknown>): did not find expected alphabetic or numeric character while scanning an alias at line 3 column 1
---
## 🧩 問題概要（再掲）
* 頂点数：`N`（最大 100,000）
* 辺数：`M`（最大 100,000）
* 各辺：`(Ai, Bi, Ci)`（無向・重み付き）
* 出力：頂点 `1` から各頂点 `k` までの最短距離 `dist[k]`。到達不能なら `-1`。
---
const graph: [number, number][][] = Array.from({ length: N }, () => []);
for (let i = 1; i <= M; i++) {
const [a, b, c] = input[i].split(' ').map(Number);
graph[a - 1].push([b - 1, c]);
graph[b - 1].push([a - 1, c]);
}入力：
1 2 4
1 3 2
2 4 1
構築されるグラフ（0-indexed）：
graph[0] = [[1,4], [2,2]] // 頂点1→ 頂点2へ4, 頂点3へ2
graph[1] = [[0,4], [3,1]] // 頂点2→ 頂点1へ4, 頂点4へ1
graph[2] = [[0,2]]
graph[3] = [[1,1]]
📘 これは「隣接リスト形式」で、各ノードの接続先とコストを記録しています。
const dist: number[] = Array(N).fill(Infinity);
dist[0] = 0;dist = [0, Infinity, Infinity, Infinity] // 頂点1までの距離は0、それ以外は未確定
pq.push([0, 0]); // [距離, 頂点]MinHeap:
┌────────────┐
│ [0, 0] │ ← 頂点0（1番）までの距離0
└────────────┘
while (pq.size() > 0) {
const [currentDist, u] = pq.pop()!;
...
}グラフ：
1 --2-- 3
|
4
|
2 --1-- 4
dist = [0, ∞, ∞, ∞]
pq = [ [0, 0] ]
-
ヒープから
[0, 0]を取り出す（距離0で頂点0） -
隣接は：
- 頂点1 → 頂点2へ距離4 → 更新（0+4=4）
- 頂点1 → 頂点3へ距離2 → 更新（0+2=2）
dist = [0, 4, 2, ∞]
pq = [ [2, 2], [4, 1] ] ← 小さい順
- 取り出し：
[2, 2] - 隣接：頂点3→頂点1（もう処理済み）→スキップ
- 取り出し：
[4, 1] - 隣接：頂点2→頂点4（コスト1）→ 4+1=5 →
dist[3] = 5
dist = [0, 4, 2, 5]
pq = [ [5, 3] ]
- 隣接：頂点4→頂点2（すでに距離小さい）→スキップ
すべての頂点を訪問し、dist 配列に最短距離が記録される。
for (const d of dist) {
console.log(d === Infinity ? -1 : d);
}例：
0
4
2
5
[start]
↓
pop 最短距離ノード
↓
各隣接ノードの距離を比較
↓
更新されたら push（次の候補）
↓
MinHeapで最小距離から処理！
| 図示処理 | 対応コード |
|---|---|
| グラフの構築 | graph[a - 1].push([b - 1, c]) |
| ヒープ初期化 | pq.push([0, 0]) |
| 最短距離更新 | if (dist[v] > d + cost) |
| 未到達チェック | d === Infinity ? -1 : d |
| 最短経路探索本体 | while (pq.size() > 0) { ... } |
| 提出日時 | 問題 | ユーザ | 言語 | 得点 | コード長 | 結果 | 実行時間 | メモリ | |
|---|---|---|---|---|---|---|---|---|---|
| 2025-06-18 22:28:55 | A64 - Shortest Path 2 | myoshizumi | PHP (php 8.2.8) | 1000 | 2220 Byte | AC | 483 ms | 110672 KiB | 詳細 |
| 2025-06-18 15:53:07 | A64 - Shortest Path 2 | myoshizumi | Go (go 1.20.6) | 1000 | 1621 Byte | AC | 324 ms | 22880 KiB | 詳細 |
| 2025-06-18 15:38:06 | A64 - Shortest Path 2 | myoshizumi | Python (CPython 3.11.4) | 1000 | 708 Byte | AC | 525 ms | 51944 KiB | 詳細 |
| 2025-06-18 15:22:44 | A64 - Shortest Path 2 | myoshizumi | TypeScript 5.1 (Node.js 18.16.1) | 1000 | 2437 Byte | AC | 639 ms | 132688 KiB | 詳細 |
| 2025-06-18 13:10:56 | A64 - Shortest Path 2 | myoshizumi | JavaScript (Node.js 18.16.1) | 1000 | 2220 Byte | AC | 757 ms | 132988 KiB | 詳細 |