Overview

This problem requires finding the shortest path (minimum fare) from station \(1\) to station \(N\) in a weighted undirected graph, and checking whether the result is within the budget \(K\).

Analysis

The key points for solving this problem are the following \(2\) items:

1. Reduction to the shortest path problem The condition states “determine whether there exists a route with a total fare of \(K\) yen or less, and find its minimum value.” This means we can simply find the minimum fare from station \(1\) to station \(N\), and then check whether the result is \(K\) or less. If even the minimum fare exceeds the budget, then any route will exceed the budget.

2. Choosing the appropriate algorithm The fare of each route (edge weight) is a positive integer of \(1\) or more. To solve the “single-source shortest path problem on a graph with non-negative weights,” Dijkstra’s algorithm is optimal.

   • Breadth-first search (BFS) can only be used when all edge weights are the same (e.g., all \(1\)).
   • Bellman-Ford algorithm can also solve this, but its time complexity is \(O(NM)\), which will not meet the time limit under the given constraints (\(N=10^5, M=2 \times 10^5\)).

Algorithm

Using Dijkstra’s algorithm, we solve the problem with the following steps:

1. Graph construction: Create an adjacency list with each station as a vertex and each route as an edge. Since travel is bidirectional, for each route \((U_i, V_i, C_i)\), store both directions \(U_i \to V_i\) and \(V_i \to U_i\).
2. Initialization:
   • Prepare an array dist to hold the minimum fare from station \(1\) to each station, and initialize all values to infinity (\(\infty\)).
   • Set dist[1] = 0.
   • Prepare a priority queue and add (fare 0, station 1).
3. Search:
   • Extract the station with the current minimum fare from the priority queue.
   • If the fare of the extracted station is greater than the already recorded dist value, skip it.
   • Calculate the total fare when traveling from that station to each adjacent station. If it is less than the current dist, update it and add the entry to the priority queue.
4. Judgment:
   • After the search is complete, if dist[N] is \(K\) or less, output that value; otherwise, output -1.

Complexity

• Time complexity: \(O(M \log N)\)
  • In Dijkstra’s algorithm, each edge is examined at most once, and each priority queue operation costs \(\log N\), resulting in an overall complexity of \(O(M \log N)\). This runs sufficiently fast under the given constraints.
• Space complexity: \(O(N + M)\)
  • The adjacency list stores information for \(M\) routes, and the distance array stores \(N\) elements, resulting in \(O(N + M)\).

Implementation Tips

• Fast input/output: Since \(M\) can be as large as \(2 \times 10^5\), in Python, reading all input at once using sys.stdin.read().split() can reduce execution time.

• Priority queue: Python’s heapq module provides a min-heap, so by storing tuples of (cost, vertex), the vertex with the minimum cost can always be extracted efficiently.

• Early termination: If the fare at the time of extraction from the priority queue already exceeds the budget \(K\), pruning by skipping further exploration can eliminate unnecessary computation.

  Source Code

import sys
import heapq

def solve():
    # 入力をすべて読み込み、イテレータを使用して高速に処理する
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    it = iter(input_data)
    try:
        n = int(next(it))
        m = int(next(it))
        k = int(next(it))
    except StopIteration:
        return
    
    # 隣接リスト形式でグラフを構築（双方向）
    adj = [[] for _ in range(n + 1)]
    for _ in range(m):
        try:
            u = int(next(it))
            v = int(next(it))
            c = int(next(it))
            adj[u].append((v, c))
            adj[v].append((u, c))
        except StopIteration:
            break
            
    # ダイクストラ法を用いて駅1から各駅への最小運賃を求める
    # dist[i] は駅1から駅iまでの最小運賃を格納する
    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
        
        # 現在の運賃がすでに予算 K を超えている場合、この経路をさらに進めても予算内に収まらない
        if d > k:
            continue
            
        # 隣接する駅を探索
        for v, cost in adj[u]:
            new_dist = d + cost
            if new_dist < dist[v]:
                dist[v] = new_dist
                heapq.heappush(pq, (new_dist, v))
                
    # 駅Nまでの最小運賃を取得
    ans = dist[n]
    
    # 最小運賃が予算 K 以下であるか判定
    if ans <= k:
        print(ans)
    else:
        print("-1")

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3-flash-thinking.