概要

交差点と道路からなるグラフ上で、混雑した交差点（次数が \(K\) 以上）を通過する際に追加コストがかかる条件のもと、交差点 \(1\) から交差点 \(N\) への最短時間を求める問題です。

考察

重要な気づき

1. 各道路の移動コストは \(1\) 分ですが、途中の交差点（\(1\) と \(N\) を除く）に到着したとき、その交差点の次数（接続する道路の本数）が \(K\) 以上なら追加で \(1\) 分かかります。

2. つまり、ある辺 \((u, v)\) を通って交差点 \(v\) に到着するときのコストは：

   • 基本コスト：\(1\)（道路の移動時間）
   • 追加コスト：\(v\) が始点 \(1\) でも終点 \(N\) でもなく、\(\text{degree}(v) \geq K\) なら \(+1\)

3. このように辺ごとのコストが一律ではない（到着先の次数によって変わる）ため、単純なBFSでは解けません。

なぜ単純なBFSではダメか

BFS は全ての辺のコストが等しい場合にのみ最短距離を正しく求められます。本問題では、辺を渡った先の交差点が混雑しているかどうかでコストが \(1\) または \(2\) に変わるため、辺の重みが不均一です。そのため、重み付きグラフの最短経路問題として扱う必要があります。

アルゴリズム

ダイクストラ法を用いて解きます。

1. グラフの構築: 各交差点の隣接リストと次数（degree）を求めます。

2. 辺のコスト定義: 交差点 \(u\) から交差点 \(v\) に移動するとき：

   • コスト \(= 1\)（道路の通過時間）
   • もし \(v \neq 1\) かつ \(v \neq N\) かつ \(\text{degree}(v) \geq K\) ならば、コスト \(= 2\)（追加の \(1\) 分を加算）

3. ダイクストラ法の実行: 交差点 \(1\) を始点とし、優先度付きキュー（最小ヒープ）を使って最短距離を求めます。

4. 結果の出力: 交差点 \(N\) への最短距離を出力します。到達不可能なら -1 を出力します。

具体例

例えば \(N=4, M=4, K=3\) で、辺が \((1,2), (1,3), (2,3), (3,4)\) の場合： - 交差点 \(3\) の次数は \(3\)（\(\geq K\)）なので混雑交差点 - 経路 \(1 \to 3 \to 4\)：コスト \(= 1 + (1+1) = 3\)（交差点 \(3\) で追加コスト発生、ただし \(3\) は途中交差点） - ただし交差点 \(3\) から \(4\) への到着は \(4 = N\) なので追加コストなし - 正しくは：\(1 \to 3\) でコスト \(1\)（交差点 \(3\) は途中なので \(+1\) で計 \(2\)）、\(3 \to 4\) でコスト \(1\)（\(N\) なので追加なし）。合計 \(3\)

計算量

• 時間計算量: \(O((N + M) \log N)\)（ダイクストラ法の標準的な計算量）
• 空間計算量: \(O(N + M)\)（グラフの隣接リストと距離配列）

実装のポイント

• 始点 \(1\) と終点 \(N\) では追加コストが発生しないことを忘れずに処理します。問題文の「出発時と到着時は通過の必要がないため」という条件です。

• 次数の計算は辺を読み込む際にカウントしておくと効率的です。

• ダイクストラ法では、既に確定した距離より大きい値でキューから取り出された場合はスキップする（if d > dist[u]: continue）ことで無駄な探索を省きます。

• 交差点 \(N\) がキューから取り出された時点で最短距離が確定するため、早期終了が可能です。

  ソースコード

import heapq
import sys
input = sys.stdin.readline

def main():
    N, M, K = map(int, input().split())
    
    graph = [[] for _ in range(N + 1)]
    degree = [0] * (N + 1)
    
    for _ in range(M):
        u, v = map(int, input().split())
        graph[u].append(v)
        graph[v].append(u)
        degree[u] += 1
        degree[v] += 1
    
    # Dijkstra from node 1 to node N
    # Cost of traversing an edge = 1 (travel time)
    # Plus, when arriving at a node v (that is not 1 and not N),
    # if degree[v] >= K, add 1 extra minute.
    
    INF = float('inf')
    dist = [INF] * (N + 1)
    dist[1] = 0
    pq = [(0, 1)]
    
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        if u == N:
            print(d)
            return
        for v in graph[u]:
            # edge cost = 1
            # arrival penalty at v: if v != 1 and v != N and degree[v] >= K, add 1
            cost = 1
            if v != 1 and v != N and degree[v] >= K:
                cost += 1
            nd = d + cost
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    
    print(-1 if dist[N] == INF else dist[N])

main()

この解説は claude4.6opus-thinking によって生成されました。