Overview

This is a problem where, given a weighted undirected graph, we need to find the shortest path from station \(1\) to station \(N\) and determine whether its fare is within the budget of \(K\) yen.

Analysis

• Key insight: To find “the minimum total fare that is at most \(K\) yen,” it suffices to find the shortest path (the path with minimum total fare) from station \(1\) to station \(N\). If the shortest path’s fare is at most \(K\), that is the answer; if even the shortest path exceeds \(K\), then no other path can achieve a fare of \(K\) or less.

• Naive approach (BFS, etc.): If all edge weights were the same, we could find the shortest path using breadth-first search (BFS). However, since the fare \(C_i\) differs for each route in this problem, BFS cannot correctly find the shortest path.

• Solution: For shortest path problems on graphs with non-negative edge weights, Dijkstra’s algorithm is suitable. Since \(C_i \geq 1\), the non-negativity condition is satisfied, and Dijkstra’s algorithm works correctly.

Algorithm

1. Graph construction: Build an adjacency list from the input. Connect each pair of stations \(U_i, V_i\) with a bidirectional edge (with fare \(C_i\)).

2. Compute shortest distances using Dijkstra’s algorithm:

   • Prepare a distance array dist, initialized with dist[1] = 0 and all others set to \(\infty\).
   • Insert (0, 1) (distance \(0\), station \(1\)) into a priority queue (min-heap).
   • Repeatedly extract the vertex \(u\) with the minimum distance from the heap. For each adjacent vertex \(v\) of \(u\), if the distance via \(u\), \(d + c\), is less than dist[v], update it and add it to the heap.
   • We can terminate early when vertex \(N\) is extracted (since dist[N] is finalized at that point).

3. Judgment and output:

   • If dist[N] \(\leq K\), output dist[N].
   • If dist[N] is \(\infty\) (unreachable) or exceeds \(K\), output -1.

Concrete example (when \(N=3, M=3, K=5\)):

Edges: 1-2 (fare 3), 2-3 (fare 2), 1-3 (fare 6)

• Path \(1 \to 2 \to 3\): fare \(3 + 2 = 5\) (\(\leq K\))
• Path \(1 \to 3\): fare \(6\) (\(> K\))
• The shortest is \(5\), which is within the budget, so the answer is \(5\).

Complexity

• Time complexity: \(O((N + M) \log N)\)
  • This is the standard complexity of Dijkstra’s algorithm. Each heap operation takes \(O(\log N)\), and at most one heap insertion is performed per edge.
• Space complexity: \(O(N + M)\)
  • The adjacency list uses \(O(N + M)\), the distance array uses \(O(N)\), and the heap contains at most \(O(M)\) elements.

Implementation Notes

• Fast input using sys.stdin.buffer.read(): In Python, standard input reading tends to be slow, so bulk reading is used for speedup.

• Duplicate check when extracting from the heap: The check if d > dist[u]: continue prevents reprocessing vertices that have already been finalized with a shorter distance. Without this, the time complexity degrades.

• Early termination: Since the shortest distance is finalized when vertex \(N\) is extracted from the heap, if u == N: break eliminates unnecessary exploration.

• Since the fare \(C_i\) can be up to \(10^9\) and the number of edges can be up to \(2 \times 10^5\), the shortest distance can be on the order of \(10^{14}\). In Python, there is no integer overflow, so no special handling is needed. However, in other languages, you need to use long long types.

  Source Code

import heapq
import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    K = int(input_data[idx]); idx += 1
    
    graph = [[] for _ in range(N + 1)]
    for i in range(M):
        U = int(input_data[idx]); idx += 1
        V = int(input_data[idx]); idx += 1
        C = int(input_data[idx]); idx += 1
        graph[U].append((V, C))
        graph[V].append((U, C))
    
    # Dijkstra's algorithm from node 1 to node N
    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:
            break
        for v, c in graph[u]:
            nd = d + c
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    
    if dist[N] <= K:
        print(dist[N])
    else:
        print(-1)

main()

This editorial was generated by claude4.6opus-thinking.