概要

この問題は、特定の頂点間にコストが変化する辺を持つグラフにおいて、最短経路を求める問題です。一部の辺についてコストが倍になる制約があります。

考察

まず、これは典型的な「重み付きグラフにおける最短経路探索」の問題であり、ダイクストラ法が有効です。

しかし単純にダイクストラ法を適用するだけでは不十分です。というのも、一部の道路（辺）については通行時間が通常の2倍になるからです。つまり、「どの辺を通ったか」によってもコストが変わってくるため、単純な頂点ごとの距離管理だけでは正しく求められません。

ただ、今回の問題では「訪問済みかどうか」といった拡張状態を考える必要はありません。なぜなら、各辺のコストはその辺自体の属性として事前にわかっているため、ダイクストラ法の中で辺を処理する際に「この辺が速度規制対象かどうか」を見て、適切にコストを2倍にして計算すればよいからです。

また、制約より \( N, M \leq 2 \times 10^5 \) となっており、単純な全探索では間に合わないため、効率的なアルゴリズムであるダイクストラ法を使う必要があります。

さらに、頂点 \(1\) から \(N\) に到達できない可能性もあるので、その場合は -1 を出力する必要があります。

アルゴリズム

ダイクストラ法（Dijkstra’s algorithm）を使用します。

1. 各辺の情報を (u, v, w) として保存し、隣接リスト形式でも辺のインデックスを一緒に持たせるようにしておきます。
2. 速度規制の対象となる辺の番号をセットで持っておき、ある辺が規制対象かどうかを高速に判定できるようにします。
3. ダイクストラ法により、始点（頂点 \(1\)）からの最短距離を管理しながら探索します：
   • 優先度付きキューを使い、現在の最小コストを持つノードを取り出して処理します。
   • 取り出したノードから伸びる辺について、規制対象であればコストを2倍にして遷移します。
4. 頂点 \(N\) への最短距離が確定した時点でその値を出力します。
5. 探索が終わっても頂点 \(N\) に到達できなければ -1 を出力します。

計算量

• 時間計算量: \( O((N + M) \log N) \)
• 空間計算量: \( O(N + M) \)

ダイクストラ法の典型計算量であり、優先度付きキューによる実装なのでログオーダーが乗ります。

実装のポイント

• 辺の情報を保持する際に、インデックスも一緒に保存することで後で速度規制対象か判定できます。

• 速度規制対象の辺番号は0-indexedに揃えることで実装ミスを防ぎます。

• ダイクストラ法の実装では、すでに更新されたノードを再度処理しないよう枝刈りを入れると効率的です。

• 到達不能ケースへの対応忘れに注意しましょう。

  ソースコード

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
    
    edges = []
    graph = [[] for _ in range(N+1)]
    
    for i in range(M):
        u = int(data[idx]); idx += 1
        v = int(data[idx]); idx += 1
        w = int(data[idx]); idx += 1
        edges.append((u, v, w))
        graph[u].append((v, i))
        graph[v].append((u, i))
    
    speed_limited = set()
    if K > 0:
        for _ in range(K):
            c = int(data[idx]) - 1; idx += 1  # 0-indexed
            speed_limited.add(c)
    
    # Dijkstra: (distance, node)
    dist = [1 << 60] * (N + 1)
    dist[1] = 0
    pq = [(0, 1)]
    
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        if u == N:
            print(d)
            return
        for v, edge_idx in graph[u]:
            edge = edges[edge_idx]
            cost = edge[2] * 2 if edge_idx in speed_limited else edge[2]
            nd = d + cost
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    
    print(-1)

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。