概要

地点1から地点Nまで、一部の道路が通常の2倍の時間がかかる条件下での最短経路を求める問題です。

考察

この問題は、通常の最短経路問題に「特定の道路だけコストが2倍になる」という制約が加わったものです。各道路は通常時と制限時の2通りのコストを持つため、単純にダイクストラ法を適用すれば解くことができます。各頂点への最短距離を記録しながら、道路の状態（制限対象かどうか）に応じて適切なコストを計算して進めばよいです。

アルゴリズム

ダイクストラ法を用いて最短経路を求めます。各頂点から隣接する頂点への移動において、使用する道路が速度規制対象（入力で与えられたK本の道路）かどうかを判定し、対応するコストを計算します。

1. グラフを隣接リスト形式で構築する（各頂点から(隣接頂点, 重み, 道路ID)のタプルを格納）
2. 速度規制対象の道路IDを集合として保持する
3. ダイクストラ法を実行：
   • 始点（地点1）の距離を0、それ以外を十分大きな値で初期化
   • 優先度付きキューを用いて、未確定の頂点の中から最短距離の頂点を選択
   • 選択した頂点から伸びる各辺について、道路IDが規制対象集合に含まれるか確認
   • 規制対象ならコストを2倍、そうでなければ通常コストで新しい距離を計算
   • 計算した距離が現在の距離より短ければ更新し、キューに追加

計算量

• 時間計算量: \(O((N + M) \log N)\)
  • ダイクストラ法の標準的な計算量です。各頂点と辺を高々1回処理し、優先度付きキュー操作に \(\log N\) 時間かかります
• 空間計算量: \(O(N + M)\)
  • グラフの表現に \(O(N + M)\)、距離配列に \(O(N)\)、優先度付きキューに \(O(N)\) が必要です

実装のポイント

• 道路IDと規制対象の対応を高速に判定するため、集合型を使用

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

• 入力データが大きいため、sys.stdin.read()で一度に読み込む

• ダイクストラ法で同じ頂点への重複処理を防ぐため、距離が更新されたときのみキューに追加

  ソースコード

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)]
    edges = {}
    
    for i in range(1, m+1):
        u = int(next(it)); v = int(next(it)); w = int(next(it))
        edges[i] = (u, v, w)
        graph[u].append((v, w, i))
        graph[v].append((u, w, i))
    
    restricted = set()
    if k > 0:
        for _ in range(k):
            c = int(next(it))
            restricted.add(c)
    
    INF = 10**18
    dist = [INF] * (n+1)
    dist[1] = 0
    heap = [(0, 1)]
    
    while heap:
        time, node = heapq.heappop(heap)
        if time != dist[node]:
            continue
        if node == n:
            break
            
        for neighbor, w, edge_id in graph[node]:
            if edge_id in restricted:
                new_time = time + 2 * w
            else:
                new_time = time + w
                
            if new_time < dist[neighbor]:
                dist[neighbor] = new_time
                heapq.heappush(heap, (new_time, neighbor))
                
    if dist[n] == INF:
        print(-1)
    else:
        print(dist[n])

if __name__ == "__main__":
    main()

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