概要

この問題は、与えられた鉄道ネットワークにおいて、駅1から駅Nまで予算K円以下で移動できる経路の存在を判定し、存在する場合は最小運賃を求める問題です。

考察

素朴なアプローチとして、すべての経路を探索する方法が考えられますが、グラフのサイズが最大で駅数\(N=10^5\)、路線数\(M=2×10^5\)と大きいため、全探索は現実的ではありません。また、運賃が非負であることから、ダイクストラ法が適用できます。ただし、予算K円以下の制約があるため、コストがKを超える経路は探索から除外することで効率化できます。

アルゴリズム

ダイクストラ法を用いて、駅1からの最小運賃を計算します。各駅への最小運賃を保持する配列distを初期化し、優先度付きキューを使用してコストが小さい順に探索します。探索中に現在のコストと辺のコストの和がK円を超える場合は、その経路を無視します。駅Nに到達した時点で、コストがK以下であればその値を出力し、そうでなければ-1を出力します。

計算量

• 時間計算量: \(O((N + M) \log N)\)（ダイクストラ法の計算量）
• 空間計算量: \(O(N + M)\)（グラフと距離配列のためのメモリ）

実装のポイント

• 大きな数値（\(10^{18}\)）を無限大として使用

• 入力データの読み込みにsys.stdin.readを使用して効率化

• 優先度付きキュー（ヒープ）を使用して最小コストの経路から探索

• コストがKを超える経路はキューに追加しないことで無駄な探索を回避

• 駅Nに到達した時点で早期終了（break）することで効率化（必須ではありませんが最適化）

  ソースコード

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()

この解説は deepseekv3 によって生成されました。