Overview

This problem asks you to find the minimum total fare (shortest distance) from station \(1\) to station \(N\), and output that value if it is within the budget of \(K\) yen, or -1 if it exceeds the budget.

Analysis

• Each route has a fare \(C_i\), which can be regarded as an “edge weight (cost).” Stations are “vertices” and routes are “undirected edges,” forming a weighted graph.
• Although you may pass through the same station multiple times, since all fares are positive (\(C_i \ge 1\)), taking unnecessary detours only increases the cost. Therefore, the “minimum fare from station \(1\) to station \(N\)” can be defined as a standard shortest path problem.

Why naive approaches are difficult

• If you try to enumerate paths using DFS/BFS to check “whether a path within budget \(K\) exists,” the number of paths explodes in graphs with many branches (this is especially dangerous since you can visit the same station any number of times). It won’t finish in a reasonable time (TLE).
• BFS can find the path with the minimum number of edges (moves), but in this problem we want to minimize the “total fare,” and since edges have weights, BFS cannot produce the correct answer (WA).

Solution approach

• Since all edge weights are positive, Dijkstra’s algorithm can be used for shortest paths.
• Additionally, since there is an upper limit of “\(K\) yen” in this problem:
  • States where the distance (total fare) exceeds \(K\) are meaningless to explore (from there onward, the total will always remain above \(K\)).

We can use this property to prune the search or suppress transitions.

Algorithm

Use Dijkstra’s algorithm to find the minimum fare dist[v] from station \(1\).

1. Build the graph using an adjacency list (since \(N\) can be large, an adjacency matrix is not feasible).
2. Initialize dist[1]=0 and all others to a sufficiently large value (INF).
3. Insert (0, 1) into a priority queue (min-heap).
4. Extract “the station u with the current minimum fare d” from the heap and do the following:
   • If the extracted (d, u) is outdated information, ignore it (d != dist[u]).
   • If d > K, then all subsequent extracted d values will be even larger, so terminate the search (unreachable).
   • If u == N, then by the property of Dijkstra’s algorithm, d is the minimum fare, so output it and terminate.
   • For each adjacent edge \((u \to v)\) with fare \(w\), compute nd = d + w:
     • Update and insert into the heap only when nd <= K and nd < dist[v].
5. If station \(N\) is never finalized, output -1.

The key property of Dijkstra’s algorithm here is that “the answer is determined the moment station \(N\) is extracted from the heap” (because all weights are positive).

Complexity

• Time complexity: \(O((N+M)\log N)\)
  (Dijkstra’s algorithm. The nd <= K pruning may make it even faster in practice.)
• Space complexity: \(O(N+M)\)
  (Adjacency list, distance array, and heap.)

Implementation Notes

• INF should be set sufficiently large, such as 10**30, since fares of up to \(10^9\) can be added up to \(10^5\) times.

• Including if d != dist[u]: continue is important to discard outdated states (distances before updates) in the heap; otherwise, unnecessary processing increases.

• We can break when d > K because the values of d extracted from the heap are always non-decreasing (extracted in order from smallest).

• Adding the condition nd <= K during transitions prevents budget-exceeding states from being pushed onto the heap, improving performance.

  Source Code

import sys
import heapq

def main():
    input = sys.stdin.buffer.readline
    N, M, K = map(int, input().split())
    g = [[] for _ in range(N + 1)]
    for _ in range(M):
        u, v, c = map(int, input().split())
        g[u].append((v, c))
        g[v].append((u, c))

    INF = 10**30
    dist = [INF] * (N + 1)
    dist[1] = 0
    hq = [(0, 1)]

    while hq:
        d, u = heapq.heappop(hq)
        if d != dist[u]:
            continue
        if d > K:
            break
        if u == N:
            print(d)
            return
        for v, w in g[u]:
            nd = d + w
            if nd <= K and nd < dist[v]:
                dist[v] = nd
                heapq.heappush(hq, (nd, v))

    print(-1)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.