Overview

In an undirected graph, we want to find the shortest path from vertex \(1\) to vertex \(N\). However, when arriving at a vertex, if the number of edges connected to that vertex is \(K\) or more, an additional \(1\) minute is required to pass through. We need to find the shortest time under this condition.

Analysis

This problem is not a simple shortest path problem (e.g., BFS), but rather a shortest path problem where “costs change dynamically.”

Key Observations

• The travel time for each road is fixed at \(1\) minute, but if the degree of the departing vertex is \(K\) or more, an additional \(1\) minute is incurred.
• However, at the start point (vertex \(1\)) and the goal point (vertex \(N\)), no additional time is incurred.
• Therefore, the cost of moving from vertex \(u\) to an adjacent vertex \(v\) is determined as follows: $\( \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} \)$

Why Doesn’t a Naive Approach Work?

• Simply using BFS assumes “cost is always 1,” so it cannot account for the additional time due to congestion, leading to incorrect answers.
• Also, exhaustive search with DFS would not finish in time since the number of vertices and edges can be up to \(2 \times 10^5\).

Solution

• Maintain the “current shortest time” for each vertex and find the shortest path using Dijkstra’s algorithm.
• Dijkstra’s algorithm can efficiently find shortest paths in graphs with non-negative edge weights.

Algorithm

1. Preprocessing
   • Compute the degree of each vertex in advance.
2. Applying Dijkstra’s Algorithm
   • Use a priority queue (heap) to manage (current time, vertex number).
   • Initialize with distance from vertex \(1\): dist[0] = 0.
3. Transitions
   • When moving from vertex \(u\) to an adjacent vertex \(v\), compute the following cost:
     • Movement cost: \(1\)
     • Additional cost: \(+1\) if the degree of \(u\) is \(K\) or more and \(u \ne 1\), \(u \ne N\)
   • If the new distance is less than the current record, update it and add to the priority queue.
4. Termination Condition
   • Output the distance at the point when vertex \(N\) is reached.
   • If it is never reached, output -1.

Complexity

• Time complexity: \(O((N + M) \log N)\)
  (Heap operations in Dijkstra’s algorithm are performed for each edge and vertex)
• Space complexity: \(O(N + M)\)
  (Adjacency list, degree array, distance array, etc.)

Implementation Notes

• Using 0-indexed vertex numbers makes array access simpler.

• Note that the degree check is performed on the departing vertex \(u\) (not the destination).

• Since no additional time is incurred at the start and goal points, make sure the conditional branching is accurate.

• Efficiency can be improved by adding pruning that skips vertices whose shortest distance has already been updated when popped from the heap.

  Source Code

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()

This editorial was generated by qwen3-coder-480b.