Overview

This problem asks us to determine whether there exists a route from station 1 to station N within a budget of K yen in a given railway network, and if so, to find the minimum fare.

Analysis

A naive approach would be to explore all possible routes, but since the graph size can be as large as \(N=10^5\) stations and \(M=2×10^5\) routes, exhaustive search is not practical. Furthermore, since fares are non-negative, Dijkstra’s algorithm can be applied. However, due to the constraint of a budget of K yen or less, we can improve efficiency by excluding routes whose cost exceeds K from the search.

Algorithm

We use Dijkstra’s algorithm to compute the minimum fare from station 1. We initialize an array dist that holds the minimum fare to each station, and use a priority queue to explore routes in order of increasing cost. During the search, if the sum of the current cost and an edge’s cost exceeds K yen, we ignore that route. When we reach station N, if the cost is K or less, we output that value; otherwise, we output -1.

Complexity

• Time complexity: \(O((N + M) \log N)\) (complexity of Dijkstra’s algorithm)
• Space complexity: \(O(N + M)\) (memory for the graph and distance array)

Implementation Notes

• Use a large value (\(10^{18}\)) as infinity

• Use sys.stdin.read for efficient input reading

• Use a priority queue (heap) to explore routes starting from the minimum cost

• Avoid unnecessary exploration by not adding routes whose cost exceeds K to the queue

• Early termination (break) upon reaching station N for efficiency (not required but an optimization)

  Source Code

import heapq
import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        print(-1)
        return
        
    it = iter(data)
    n = int(next(it)); m = int(next(it)); K = int(next(it))
    graph = [[] for _ in range(n+1)]
    
    for _ in range(m):
        u = int(next(it)); v = int(next(it)); c = int(next(it))
        graph[u].append((v, c))
        graph[v].append((u, c))
    
    INF = 10**18
    dist = [INF] * (n+1)
    dist[1] = 0
    heap = [(0, 1)]
    
    while heap:
        d, node = heapq.heappop(heap)
        if d != dist[node]:
            continue
        if node == n:
            break
        for neighbor, cost in graph[node]:
            new_d = d + cost
            if new_d < dist[neighbor] and new_d <= K:
                dist[neighbor] = new_d
                heapq.heappush(heap, (new_d, neighbor))
    
    if dist[n] <= K:
        print(dist[n])
    else:
        print(-1)

if __name__ == "__main__":
    main()

---

This editorial was generated by deepseekv3.