概要

この問題は、\(N\) 個の交差点と \(M\) 本の道路からなるグラフにおいて、交差点 \(1\) から交差点 \(N\) までの最短所要時間を求める問題です。 通常の最短経路問題と異なる点は、「次数（接続されている道路の本数）が \(K\) 以上の交差点を通過する際に、追加で 1 分かかる」という特殊なコスト規則があることです。

考察

1. コストの整理

移動にかかる時間を整理すると、以下のようになります。 - 道路を 1 本通る：必ず 1 分 かかる。 - 交差点 \(i\) に到着し、そこから次の交差点へ向かう（通過する）： - 交差点 \(i\) の次数が \(K\) 以上なら、追加で 1 分 かかる。 - ただし、出発地点（交差点 \(1\)）と到着地点（交差点 \(N\)）ではこの追加時間は発生しない。

この「通過時の追加時間」は、「その交差点に進入する際にかかるコスト」として解釈すると考えやすくなります。 具体的には、交差点 \(u\) から交差点 \(v\) へ移動する際、かかるコストを以下のように定義します。 - \(v = N\) のとき：コスト = \(1\)（道路の分のみ） - \(v \neq N\) かつ \(v\) の次数 \(\ge K\) のとき：コスト = \(1 + 1 = 2\)（道路 + 追加時間） - それ以外：コスト = \(1\)（道路の分のみ） ※出発点である交差点 1 の次数が \(K\) 以上であっても、そこから「出発」する際には追加時間はかからないため、考慮不要です。

2. なぜ単純な BFS では解けないか

通常の幅優先探索（BFS）は、すべての辺のコストが等しい場合にのみ最短経路を正しく求められます。 今回の問題では、移動コストが \(1\) の場合と \(2\) の場合が混在しているため、単純な BFS ではなく、ダイクストラ法（Dijkstra’s algorithm） を使用する必要があります。

アルゴリズム

1. グラフの構築と次数の計算: 隣接リスト形式でグラフを保持し、同時に各頂点の次数（つながっている辺の数）を数えます。
2. 追加コストの判定: 各交差点 \(i \in \{2, \dots, N-1\}\) について、次数が \(K\) 以上かどうかを確認し、追加コストが発生するかをフラグや配列で持っておきます。
3. ダイクストラ法による最短経路探索:
   • 優先度付きキュー（ヒープ）を用意し、(経過時間, 現在の交差点) を管理します。
   • 始点（交差点 1）の時間を 0 とし、キューに追加します。
   • キューから最小時間 \(d\) の頂点 \(u\) を取り出し、隣接する頂点 \(v\) に対して時間を更新します：
     • new_time = d + 1 + (v が中間地点かつ混雑していれば 1、そうでなければ 0)
     • new_time がこれまでの dist[v] より小さければ更新し、キューに追加します。
4. 結果の出力: 交差点 \(N\) にたどり着いた時の最小時間を出力します。一度もたどり着けなかった場合は -1 を出力します。

計算量

• 時間計算量: \(O((N + M) \log N)\)
  • 次数の計算に \(O(M)\)、ダイクストラ法に \(O((N + M) \log N)\) かかります。制約の \(N, M \leq 2 \times 10^5\) に対して十分高速に動作します。
• 空間計算量: \(O(N + M)\)
  • 隣接リストと距離配列、次数配列を保持するために \(O(N + M)\) のメモリを使用します。

実装のポイント

• 入力の高速化: \(N, M\) が大きいため、Python では sys.stdin.read().split() などを用いて一括で入力を読み込むと実行時間を短縮できます。

• 追加コストの除外条件: 問題文にある「出発地点 1 と到着地点 \(N\) では追加時間がかからない」という条件を忘れないようにします。コード上では、交差点 \(N\) を判定から外すか、コスト計算時に \(v=N\) の場合を特別扱いすることで対応できます。

• ダイクストラ法の基本: すでに確定した最短距離よりも大きいコストでキューから取り出された要素は無視する（if d > dist[u]: continue）ことで、無駄な計算を防ぎます。

  ソースコード

import sys
import heapq

def solve():
    # Fast input reading using sys.stdin.read().split()
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    it = iter(input_data)
    try:
        N = int(next(it))
        M = int(next(it))
        K = int(next(it))
    except StopIteration:
        return
    
    # Building the adjacency list and calculating the degree of each intersection
    adj = [[] for _ in range(N + 1)]
    degree = [0] * (N + 1)
    for _ in range(M):
        try:
            u = int(next(it))
            v = int(next(it))
            adj[u].append(v)
            adj[v].append(u)
            degree[u] += 1
            degree[v] += 1
        except StopIteration:
            break
            
    # extra_cost[v] is 1 if intersection v incurs an additional minute.
    # This applies only when "passing through" an intersection, meaning it
    # must be an intermediate node in the path. The problem states that 
    # additional time is not required at the starting intersection (1) 
    # or the arrival intersection (N).
    extra_cost = [0] * (N + 1)
    for i in range(2, N):
        if degree[i] >= K:
            extra_cost[i] = 1
            
    # Dijkstra's algorithm to find the minimum time from intersection 1 to N
    # dist[i] stores the minimum time taken to reach intersection i
    INF = 10**18
    dist = [INF] * (N + 1)
    dist[1] = 0
    pq = [(0, 1)] # (current_time, current_intersection)
    
    while pq:
        d, u = heapq.heappop(pq)
        
        # If a shorter path to u has already been processed, skip this one
        if d > dist[u]:
            continue
        
        # If we have reached the destination intersection N, output the time
        if u == N:
            print(d)
            return
        
        for v in adj[u]:
            # The time to travel along any road is 1 minute.
            # If the destination intersection v is an intermediate intersection
            # (i.e., v is not N), we add the extra_cost associated with v.
            # If v is N, extra_cost[v] is already 0.
            new_time = d + 1 + extra_cost[v]
            if dist[v] > new_time:
                dist[v] = new_time
                heapq.heappush(pq, (new_time, v))
                
    # If intersection N is unreachable from intersection 1
    print("-1")

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-thinking によって生成されました。