概要

各道路の移動は \(1\) 分で、到着する交差点（ただし \(1\) と \(N\) を除く）が「混雑（次数 \(\ge K\)）」なら追加で \(1\) 分かかるとき、交差点 \(1\) から \(N\) への最短時間を求める問題です。

考察

この問題の本質は「辺を渡るコストが、行き先の頂点によって変わる」という点です。

• 交差点 \(v\) の接続道路数（次数）を \(\deg(v)\) とすると、
  \(v \neq 1, N\) かつ \(\deg(v) \ge K\) のとき、\(v\) に着いた瞬間に追加で \(1\) 分かかります。
• したがって、交差点 \(u\) から隣接交差点 \(v\) へ移動するコストは一律ではなく
  [ \text{cost}(u \to v) = 1 + \text{pen}(v) ] となります（\(\text{pen}(v)=1\) なら混雑、\(0\) なら非混雑）。

ここで重要なのは、最短経路問題として見たときに 重みがすべて非負（\(1\) または \(2\)） であることです。
よって BFS（辺重みが全て同じときの最短路）では正しく解けない可能性があります。

例：混雑交差点を避けると遠回りでも速いことがある
- 経路A：道路2本（移動2分）＋途中の交差点が混雑で +1 → 合計3分
- 経路B：道路3本（移動3分）＋混雑なし → 合計3分
このように「辺数最小」が「時間最小」と一致しません。

また、全経路を探索するような素朴な全探索は、\(N,M \le 2\times 10^5\) なので当然間に合いません。

そこで、重み付き最短路として標準的に ダイクストラ法を使います。

アルゴリズム

1. グラフを隣接リストで構築し、同時に各頂点の次数 \(\deg(i)\) を数える。
2. 追加時間の有無を配列 pen で前計算する。
   
   • \(i=2\) から \(N-1\) について、\(\deg(i) \ge K\) なら pen[i]=1、それ以外は 0
     
   • 交差点 \(1\) と \(N\) は問題文により常に追加なしなので pen[1]=pen[N]=0
3. ダイクストラ法で最短時間 dist を求める。
   • 初期：dist[1]=0
   • 優先度付きキュー（最小ヒープ）から「現在もっとも早く到達できる頂点 \(u\)」を取り出す
   • 隣接頂点 \(v\) へは [ nd = dist[u] + 1 + pen[v] ] で緩和（更新）する
4. dist[N] が更新されなければ到達不能なので -1、そうでなければその値を出力。

この実装では「追加時間は 到着先 \(v\) によって決まる」点が肝です（出発元ではない）。

計算量

• 時間計算量: \(O((N+M)\log N)\)
  （ダイクストラ法：各辺の緩和とヒープ操作）
• 空間計算量: \(O(N+M)\)
  （隣接リスト、次数配列、距離配列、ヒープ）

実装のポイント

• 交差点 \(1\) と \(N\) には追加時間がかからないため、pen の設定は \(2\) 〜 \(N-1\) のみにする。

• コストは 1 + pen[v]（到着先基準）で計算する。

• ダイクストラの定番として、ヒープから取り出した (d,u) が古い情報なら continue する（d != dist[u]）。

• 入力が大きいので sys.stdin.buffer.read() を使って高速に読む。

  ソースコード

import sys
import heapq

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    it = iter(data)
    N = next(it)
    M = next(it)
    K = next(it)

    adj = [[] for _ in range(N + 1)]
    deg = [0] * (N + 1)

    for _ in range(M):
        u = next(it)
        v = next(it)
        adj[u].append(v)
        adj[v].append(u)
        deg[u] += 1
        deg[v] += 1

    pen = [0] * (N + 1)
    for i in range(2, N):
        if deg[i] >= K:
            pen[i] = 1

    INF = 10**18
    dist = [INF] * (N + 1)
    dist[1] = 0
    hq = [(0, 1)]

    while hq:
        d, u = heapq.heappop(hq)
        if d != dist[u]:
            continue
        if u == N:
            break
        for v in adj[u]:
            nd = d + 1 + pen[v]
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(hq, (nd, v))

    ans = dist[N]
    print(ans if ans < INF else -1)

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。