概要

「\(S\) から \(G\) に行き、その後 \(T\) に行く」という条件付き最短経路問題です。
重み付き無向グラフなので、地点 \(G\) から 1 回ダイクストラ法を行えば、答えは \(dist(G,S) + dist(G,T)\) で求まります。

考察

まず、高橋君の移動は必ず

1. \(S\) から \(G\) へ行く
2. \(G\) から \(T\) へ行く

の 2 段階に分けられます。

ここで重要なのは、最短時間はこの 2 つの最短距離の和になるということです。

なぜなら、どんな有効な移動経路も

• 前半：\(S \to G\)
• 後半：\(G \to T\)

に分解できます。
前半の長さは少なくとも \(S\) から \(G\) への最短距離以上、後半の長さは少なくとも \(G\) から \(T\) への最短距離以上です。

したがって、どんな経路でも全体の長さは

\(dist(S,G) + dist(G,T)\)

以上になります。
一方で、\(S \to G\) の最短経路と \(G \to T\) の最短経路をそのままつなげれば、この長さを実現できます。
よって答えは

\(dist(S,G) + dist(G,T)\)

です。

---

素朴な方法がだめな理由

「\(S\) から \(G\) を経由して \(T\) へ行く経路を全部試す」とすると、経路の数は非常に多く、到底間に合いません。

また、辺の重み \(C_i\) は最大 \(10^9\) と大きいため、普通の BFS は使えません。
重み付きグラフの最短距離なので、ダイクストラ法を使うのが定石です。

---

さらに大事な気づき

通常なら

• \(S\) から全点への最短距離
• \(G\) から全点への最短距離

を求めて、答えを \(dist_S[G] + dist_G[T]\) としてもよいです。

しかしこの問題のグラフは無向グラフなので、

\(dist(S,G) = dist(G,S)\)

が成り立ちます。
そのため、\(G\) から 1 回だけダイクストラ法をすれば十分です。

すると

• \(dist[G \to S]\)
• \(dist[G \to T]\)

の両方が手に入るので、答えはその和になります。

アルゴリズム

1. 隣接リストで無向グラフを構築する。
2. 地点 \(G\) を始点としてダイクストラ法を行う。
3. \(dist[S]\) と \(dist[T]\) を調べる。
   • どちらかが未到達なら \(-1\)
   • そうでなければ \(dist[S] + dist[T]\) を出力する

---

ダイクストラ法の流れ

• 優先度付きキューに「距離, 頂点」を入れる
• いま最も距離が小さい頂点から確定していく
• 辺を使って隣接頂点の距離を更新する

このコードでは、\(S\) と \(T\) の最短距離が両方確定した時点で打ち切っています。
最終的に必要なのはこの 2 点への距離だけなので、少しだけ効率がよくなります。

計算量

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

実装のポイント

• 頂点番号は入力では \(1\) 始まりなので、コード内では \(0\) 始まりに直しています。
• ダイクストラ法では、同じ頂点が優先度付きキューに複数回入ることがあります。
  そのため if d != dist[v]: continue で、古い情報を無視しています。
• 到達不可能かどうかは、距離配列が INF のままかで判定します。
• 辺の重みが大きいので、INF も十分大きい値（このコードでは \(10^{30}\)）にしてあります。

例えば、

• \(dist(G,S)=5\)
• \(dist(G,T)=7\)

なら、最小時間は \(5+7=12\) です。
途中で同じ地点や道路を何度通ってもよいですが、最短にしたいなら結局この和が最適になります。

ソースコード

import sys
import heapq

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return

    it = iter(data)
    N = next(it)
    M = next(it)
    S = next(it) - 1
    G = next(it) - 1
    T = next(it) - 1

    graph = [[] for _ in range(N)]
    for _ in range(M):
        u = next(it) - 1
        v = next(it) - 1
        c = next(it)
        graph[u].append((v, c))
        graph[v].append((u, c))

    INF = 10**30
    dist = [INF] * N
    dist[G] = 0
    hq = [(0, G)]
    need = 2  # S and T
    found_s = (G == S)
    found_t = (G == T)

    while hq:
        d, v = heapq.heappop(hq)
        if d != dist[v]:
            continue

        if v == S and not found_s:
            found_s = True
            need -= 1
        if v == T and not found_t:
            found_t = True
            need -= 1
        if need == 0:
            break

        for nv, w in graph[v]:
            nd = d + w
            if nd < dist[nv]:
                dist[nv] = nd
                heapq.heappush(hq, (nd, nv))

    if dist[S] >= INF or dist[T] >= INF:
        print(-1)
    else:
        print(dist[S] + dist[T])

if __name__ == "__main__":
    main()

---

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