概要

この問題は、地点 \(1\) から地点 \(K\) を経由して地点 \(N\) へ向かう際の最短時間を求める問題です。重み付き無向グラフにおいて、特定の地点を経由する最短経路を効率的に計算する必要があります。

考察

目的地までのルートを分解すると、以下の 2 つの区間に分けることができます。 1. 地点 \(1\) から地点 \(K\) までの最短経路 2. 地点 \(K\) から地点 \(N\) までの最短経路

この 2 つの区間の最短時間の合計が、全体の最短時間となります。

各道路には「通行時間」という重みがあるため、単純な幅優先探索（BFS）ではなく、ダイクストラ法を用いるのが適切です。

通常、地点 \(1\) からのダイクストラ法と地点 \(K\) からのダイクストラ法の 2 回を行うことを考えますが、この問題のグラフは「無向グラフ（双方向に通行可能）」です。無向グラフでは「地点 \(1\) から \(K\) への距離」は「地点 \(K\) から \(1\) への距離」と等しくなります。 したがって、中継拠点である地点 \(K\) を始点としてダイクストラ法を 1 回だけ実行すれば、地点 \(1\) への最短距離と地点 \(N\) への最短距離を同時に求めることができ、非常に効率的です。

アルゴリズム

1. グラフの構築: 与えられた道路情報を隣接リスト形式で保持します。
2. ダイクストラ法の実行:
   • 地点 \(K\) を始点とし、各地点への最短距離を格納する配列 dist を無限大（inf）で初期化します（dist[k] = 0）。
   • 優先度付きキュー（ヒープ）を用いて、未確定の地点のうち最も距離が近い地点から順に探索を進めます。
3. 結果の判定:
   • 地点 \(K\) から地点 \(1\) への距離 dist[1] と、地点 \(K\) から地点 \(N\) への距離 dist[n] を確認します。
   • いずれかが初期値（inf）のままなら、到達不可能と判断して -1 を出力します。
   • 両方に到達可能な場合、その和 dist[1] + dist[n] を出力します。

計算量

• 時間計算量: \(O(M \log N)\)
  • ダイクストラ法の計算量は、地点数を \(N\)、道路（辺）の数を \(M\) とすると \(O(M \log N)\) です。今回の制約（\(N, M \leq 2 \times 10^5\)）では、制限時間内に十分間に合います。
• 空間計算量: \(O(N + M)\)
  • 隣接リストの保存に \(O(N + M)\)、最短距離配列に \(O(N)\) のメモリを使用します。

実装のポイント

• 高速な入出力: \(N, M\) が大きいため、Python では sys.stdin.read().split() などを用いて一括で入力を読み込むと実行時間を短縮できます。

• 優先度付きキュー: heapq モジュールを使用することで、ダイクストラ法を効率的に実装できます。

• 到達不能の判定: どちらか一方の区間でも到達できない場合、全体のルートが成立しないため、個別にチェックする必要があります。

  ソースコード

import sys
import heapq

def solve():
    # 入力を一括で読み込み、イテレータに変換して高速化
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    it = iter(input_data)
    n = int(next(it))
    m = int(next(it))
    k = int(next(it))

    # 隣接リストの構築
    adj = [[] for _ in range(n + 1)]
    for _ in range(m):
        u = int(next(it))
        v = int(next(it))
        c = int(next(it))
        adj[u].append((v, c))
        adj[v].append((u, c))

    # 地点 K から他の全地点への最短距離をダイクストラ法で求める
    # 地点 1 から K を経由して N へ行く最短時間は、dist(1, K) + dist(K, N) となる。
    # 無向グラフなので dist(1, K) = dist(K, 1) であり、K を始点とするダイクストラ1回で済む。
    inf = float('inf')
    dist = [inf] * (n + 1)
    dist[k] = 0
    pq = [(0, k)]

    while pq:
        d, u = heapq.heappop(pq)
        
        # すでに確定している距離より大きい場合はスキップ
        if d > dist[u]:
            continue
            
        for v, cost in adj[u]:
            new_dist = d + cost
            if dist[v] > new_dist:
                dist[v] = new_dist
                heapq.heappush(pq, (new_dist, v))
    
    # Kから地点1までの距離と、Kから地点Nまでの距離を取得
    dist_k_to_1 = dist[1]
    dist_k_to_n = dist[n]
    
    # どちらかが到達不可能な場合は -1 を出力
    if dist_k_to_1 == inf or dist_k_to_n == inf:
        print("-1")
    else:
        # 1 -> K -> N の合計時間を計算して出力
        print(dist_k_to_1 + dist_k_to_n)

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-thinking によって生成されました。