概要

「\(S \rightarrow G \rightarrow T\) の順で移動する最短時間」を求める問題です。
重み付き無向グラフなので、最短経路計算にダイクストラ法を使うのが基本になります。

考察

重要なポイントは、経由点 \(G\) が必須であることです。
この条件がある最短経路は、次の2つに分けて考えられます。

1. \(S\) から \(G\) までの最短距離
2. \(G\) から \(T\) までの最短距離

全体の最短時間は、この和 [ \text{dist}(S,G) + \text{dist}(G,T) ] になります。

なぜこれでよいかというと、経路全体が \(S \to \cdots \to G \to \cdots \to T\) という形なら、前半と後半は独立に最短化できるためです。
もし前半が最短でなければ、より短い前半に置き換えて全体を短くできてしまい、最短であることに矛盾します。後半も同様です。

素朴に「\(S\) から全経路探索して \(G\) を通って \(T\) に行く最短」をやろうとすると、経路数が膨大になり現実的ではありません（指数的に増える可能性）。
また、重み付きグラフなので BFS では正しい最短距離を出せません（BFS は辺重みがすべて同じときのみ有効）。

そこで、非負重みの最短経路に強いダイクストラ法を使います。
必要なのは \(S\) 始点と \(G\) 始点の2回だけです。

アルゴリズム

1. 隣接リストで無向グラフを構築する。
2. ダイクストラ法を \(S\) から実行し、distS を得る（各頂点への最短距離）。
3. ダイクストラ法を \(G\) から実行し、distG を得る。
4. distS[G] または distG[T] が到達不能（INF）の場合は -1。
5. そうでなければ distS[G] + distG[T] を出力。

コード中の if d != dist[v]: continue は、優先度付きキューに残っている古い（不要な）情報を捨てるための定番テクニックです。

計算量

• 時間計算量: \(O((N+M)\log N)\) を2回実行するので、定数倍を除いて \(O((N+M)\log N)\)
• 空間計算量: \(O(N+M)\)（グラフ + 距離配列 + 優先度付きキュー）

実装のポイント

• 距離は最大で大きくなるため、INF = 10**30 のように十分大きい値を使う。

• 頂点番号が \(1\) 始まりなので、配列サイズを N+1 にする。

• 到達不能判定を忘れずに行う（distS[G] >= INF または distG[T] >= INF）。

  ソースコード

import sys
import heapq

def dijkstra(start, graph, n):
    INF = 10**30
    dist = [INF] * (n + 1)
    dist[start] = 0
    pq = [(0, start)]
    while pq:
        d, v = heapq.heappop(pq)
        if d != dist[v]:
            continue
        for to, w in graph[v]:
            nd = d + w
            if nd < dist[to]:
                dist[to] = nd
                heapq.heappush(pq, (nd, to))
    return dist

def main():
    input = sys.stdin.readline
    N, M, S, G, T = map(int, input().split())
    graph = [[] for _ in range(N + 1)]
    for _ in range(M):
        u, v, c = map(int, input().split())
        graph[u].append((v, c))
        graph[v].append((u, c))

    distS = dijkstra(S, graph, N)
    distG = dijkstra(G, graph, N)

    INF = 10**30
    if distS[G] >= INF or distG[T] >= INF:
        print(-1)
    else:
        print(distS[G] + distG[T])

if __name__ == "__main__":
    main()

この解説は gpt-5.3-codex によって生成されました。