Overview

Each road takes \(1\) minute to traverse, and if the intersection you arrive at (excluding \(1\) and \(N\)) is “congested” (degree \(\ge K\)), it costs an additional \(1\) minute. The problem asks for the shortest time from intersection \(1\) to intersection \(N\).

Analysis

The essence of this problem is that the cost of traversing an edge depends on the destination vertex.

• Let \(\deg(v)\) denote the number of connected roads (degree) of intersection \(v\).
  If \(v \neq 1, N\) and \(\deg(v) \ge K\), then arriving at \(v\) incurs an additional \(1\) minute.
• Therefore, the cost of moving from intersection \(u\) to adjacent intersection \(v\) is not uniform: [ \text{cost}(u \to v) = 1 + \text{pen}(v) ] where \(\text{pen}(v)=1\) if congested, \(0\) if not.

The key observation is that when viewed as a shortest path problem, all weights are non-negative (\(1\) or \(2\)).
Thus, BFS (which finds shortest paths when all edge weights are equal) may not give correct results.

Example: Avoiding congested intersections might be faster even with a detour
- Path A: 2 roads (2 minutes travel) + intermediate intersection is congested (+1) → total 3 minutes
- Path B: 3 roads (3 minutes travel) + no congestion → total 3 minutes
In this way, “minimum number of edges” does not necessarily equal “minimum time.”

Also, a naive brute-force search over all paths is clearly infeasible since \(N, M \le 2\times 10^5\).

Therefore, we use Dijkstra’s algorithm as the standard approach for weighted shortest paths.

Algorithm

1. Build the graph as an adjacency list and simultaneously count the degree \(\deg(i)\) of each vertex.
2. Precompute the additional time in an array pen.
   
   • For \(i = 2\) to \(N-1\): if \(\deg(i) \ge K\) then pen[i]=1, otherwise 0
     
   • Intersections \(1\) and \(N\) never incur additional time per the problem statement, so pen[1]=pen[N]=0
3. Find the shortest time dist using Dijkstra’s algorithm.
   • Initialize: dist[1]=0
   • Extract from the priority queue (min-heap) the vertex \(u\) that can be reached earliest
   • For each adjacent vertex \(v\), relax (update) with: [ nd = dist[u] + 1 + pen[v] ]
4. If dist[N] was never updated, the destination is unreachable so output -1; otherwise output the value.

The key point in this implementation is that “the additional time is determined by the destination \(v\)” (not the source).

Complexity

• Time complexity: \(O((N+M)\log N)\)
  (Dijkstra’s algorithm: edge relaxation and heap operations)
• Space complexity: \(O(N+M)\)
  (adjacency list, degree array, distance array, heap)

Implementation Notes

• Intersections \(1\) and \(N\) do not incur additional time, so pen is only set for vertices \(2\) through \(N-1\).

• The cost is computed as 1 + pen[v] (based on the destination).

• As standard in Dijkstra’s algorithm, when extracting (d, u) from the heap, skip it if it is outdated information (d != dist[u]).

• Since the input can be large, use sys.stdin.buffer.read() for fast reading.

  Source Code

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

This editorial was generated by gpt-5.2-high.