Overview

This problem is a shortest path problem with a cost constraint. In an undirected graph, we want to find the minimum total edge weight among all paths from the start to the end whose total edge weight is at most \(K\).

Analysis

This problem is a typical “shortest path with cost constraint” problem. A naive approach would be to perform an exhaustive search, but since the number of vertices \(N\) can be up to \(10^5\) and the number of edges \(M\) can be up to \(2 \times 10^5\), a simple exhaustive search or DFS would be too computationally expensive to finish in time.

Additionally, since visiting the same station multiple times is allowed, simple visited-flag management cannot handle this. Furthermore, since the fare upper limit \(K\) can be up to \(10^9\), it is not practical to include the cost as a DP state (neither memory nor time would suffice).

Therefore, we consider using Dijkstra’s algorithm. Dijkstra’s algorithm can efficiently find the single-source shortest path in a graph with non-negative edge weights. In this problem, since there is a condition that “the total fare must be at most \(K\) yen,” we add the condition new_cost <= K during the update step of Dijkstra’s algorithm, so that we only explore within the range that satisfies the constraint.

This allows us to avoid unnecessary exploration while finding the path that reaches the destination with the minimum fare.

Algorithm

1. Graph Construction:

   • Store each edge bidirectionally in the graph. In Python, we use an adjacency list representation.

2. Applying Dijkstra’s Algorithm:

   • Prepare an array dist to record the minimum fare from the starting point (station 1), initialized to infinity (INF), with only the start set to 0.
   • Use a priority queue (heap) to explore in the form of (current fare, current station).
   • For each node extracted from the queue, consider transitions to adjacent nodes.
   • If the new fare exceeds the budget \(K\), ignore it.
   • If the new fare is smaller than the previously recorded value, update it and add it to the heap.

3. Output the Result:

   • If dist for the destination (station \(N\)) has been updated, output that value; otherwise, output -1.

Example:

Sample input:

4 4 10
1 2 3
2 3 4
3 4 5
1 4 10

• Station 1 → 2 → 3 → 4: Cost \(3 + 4 + 5 = 12\) (exceeds budget)
• Station 1 → 4: Cost 10 (OK) → The answer is 10

Complexity

• Time complexity: \(O(M \log N)\)
  • The typical complexity of Dijkstra’s algorithm. Each edge is processed at most once, and each heap operation takes \(\log N\).
• Space complexity: \(O(N + M)\)
  • Due to the adjacency list of the graph and the distance array.

Implementation Notes

• Convert graph vertex indices to 0-indexed (since the input is 1-indexed).

• Store entries in the heap in the order (cost, node) so that entries with smaller cost are extracted first.

• Initialize the dist array with a sufficiently large value (e.g., \(10^{18}\)).

• Always include the condition new_cost <= K in the update step.

• Even when there are multiple paths to the same node, add pruning to skip nodes whose shortest distance has already been finalized.

  Source Code

import heapq
import sys

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
    
    # グラフ構築
    graph = [[] for _ in range(N)]
    for _ in range(M):
        u = int(data[idx]) - 1; idx += 1
        v = int(data[idx]) - 1; idx += 1
        c = int(data[idx]); idx += 1
        graph[u].append((v, c))
        graph[v].append((u, c))
    
    # ダイクストラ法で最小運賃を求める（コスト制限付き）
    # dist[i] := 駅1から駅i+1へのコストK以下の最小運賃
    # 無限大で初期化
    INF = 10**18
    dist = [INF] * N
    dist[0] = 0
    # (現在の運賃, 現在の駅)
    pq = [(0, 0)]
    
    while pq:
        cost, u = heapq.heappop(pq)
        if cost > dist[u]:
            continue
        for v, c in graph[u]:
            new_cost = cost + c
            if new_cost <= K and new_cost < dist[v]:
                dist[v] = new_cost
                heapq.heappush(pq, (new_cost, v))
    
    result = dist[N-1] if dist[N-1] != INF else -1
    print(result)

if __name__ == "__main__":
    main()

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