概要

無向グラフにおいて、頂点 \(1\) から頂点 \(N\) への最短経路を求めたい。ただし、各頂点に到着したときに、その頂点に接続する辺の数が \(K\) 以上であれば、通過に \(1\) 分の追加時間がかかる。この条件のもとでの最短時間を求めよ。

考察

この問題は、単純な最短経路問題（例えば BFS）ではなく、「コストが動的に変化する」最短経路問題です。

重要な観察

• 各道路の移動時間は \(1\) 分固定だが、出発する頂点の次数が \(K\) 以上であれば追加で \(1\) 分かかる。
• ただし、スタート地点（頂点 \(1\)）とゴール地点（頂点 \(N\)）では追加時間はかからない。
• よって、ある頂点 \(u\) から隣接する頂点 \(v\) へ移動するときのコストは以下のように決まる： $\( \text{cost} = \begin{cases} 1 & \text{if } u = 1 \text{ or } u = N \\ 1 + 1 = 2 & \text{if } \deg(u) \geq K \text{ and } u \ne 1, u \ne N \\ 1 & \text{otherwise} \end{cases} \)$

素朴な方法ではなぜダメか？

• 単純にBFSを使うと「コストが常に1」と仮定してしまうため、混雑による追加時間を考慮できず、誤った答えになる。
• また、DFSなどで全探索すると、頂点数・辺数が最大 \(2 \times 10^5\) のため、時間内に終わらない。

解決策

• 頂点ごとに「現在の最短時間」を持ちながら、ダイクストラ法で最短経路を求める。
• ダイクストラ法は、非負の重みを持つグラフに対して効率的に最短経路を求めることができる。

アルゴリズム

1. 前処理
   • 各頂点の次数（degree）を計算しておく。
2. ダイクストラ法の適用
   • 優先度付きキュー（ヒープ）を使用して、(現在の時間, 頂点番号) を管理。
   • 頂点 \(1\) からの距離 dist[0] = 0 として初期化。
3. 遷移
   • 頂点 \(u\) から隣接する頂点 \(v\) へ移動するとき、以下のコストを計算：
     • 移動コスト：\(1\)
     • 追加コスト：\(u\) が次数 \(K\) 以上かつ、\(u \ne 1\), \(u \ne N\) なら \(+1\)
   • 新しい距離が現在の記録より小さければ更新し、優先度付きキューに追加。
4. 終了条件
   • 頂点 \(N\) に到達した時点でその時点の距離を出力。
   • 最後まで到達できなかったら -1 を出力。

計算量

• 時間計算量: \(O((N + M) \log N)\)
  （ダイクストラ法におけるヒープ操作が各辺・頂点に対して行われる）
• 空間計算量: \(O(N + M)\)
  （隣接リスト、次数配列、距離配列など）

実装のポイント

• 頂点番号は 0-indexed にしておくと、配列アクセスが簡単になる。
• 次数のチェックは、出発元の頂点 \(u\) に対して行うことに注意（到着先ではない）。
• スタート地点とゴール地点では追加時間はかからないので、条件分岐を正確に行うこと。
• ヒープから取り出したときに、すでに最短距離が更新されていればスキップする枝刈りを入れることで効率化できる。

## ソースコード

```python
import sys
from collections import deque, defaultdict
import heapq

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1
    K = int(data[idx]); idx += 1
    
    # 隣接リストと次数の計算
    adj = [[] for _ in range(N)]
    degree = [0] * N
    
    for _ in range(M):
        u = int(data[idx]) - 1; idx += 1
        v = int(data[idx]) - 1; idx += 1
        adj[u].append(v)
        adj[v].append(u)
        degree[u] += 1
        degree[v] += 1
    
    # ダイクストラ法で最短時間を求める
    # dist[i] := 頂点 i への最短時間
    dist = [float('inf')] * N
    dist[0] = 0
    # (time, node)
    pq = [(0, 0)]
    
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        if u == N - 1:
            print(d)
            return
        
        # 次の頂点へ移動
        for v in adj[u]:
            # 移動時間: 1分 + 混雑による追加時間（出発元と目的地以外）
            cost = 1
            if u != 0 and u != N-1 and degree[u] >= K:
                cost += 1
            new_d = d + cost
            if new_d < dist[v]:
                dist[v] = new_d
                heapq.heappush(pq, (new_d, v))
    
    print(-1)

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。