概要

拠点 \(1\) から出発して拠点 \(T\) を訪れ、本社（拠点 \(1\)）に戻るまでの最短時間を、最短経路問題として解きます。

考察

この問題で求めたいのは、ある経路 [ 1 \to (\text{いくつかの拠点}) \to T \to (\text{いくつかの拠点}) \to 1 ] の最小コストです。道路は無向で、時間 \(C_i\) はどちら向きでも同じ、かつ \(C_i \ge 1\) なのでコストは非負です。

ここで重要な気づきは次の2点です。

• 「\(1\) から \(T\) へ行く部分」と「\(T\) から \(1\) に戻る部分」は、それぞれ独立に最短にできます。
  なぜなら、全ての辺の重みが非負なので、遠回りするメリットがありません（最短路部分は必ず最短路に置き換えられる）。
• 無向グラフなので [ \text{dist}(1, T) = \text{dist}(T, 1) ] が成り立ちます（\(1\to T\) の最短路を逆向きに辿れば \(T\to 1\) の経路になるため）。

したがって、答えは [ \text{dist}(1, T) + \text{dist}(T, 1) = 2 \times \text{dist}(1, T) ] になります。

素朴に「\(1\) から出て \(T\) を経由して戻る経路」を全探索すると、経路数が膨大（指数的）になり到底間に合いません。また、最短路を求める必要があるため、重み付きグラフに対して BFS を使うと WA になります。

そこで、重み付き最短路の定番である ダイクストラ法で \(1\) からの最短距離を計算し、\(T\) が到達不能なら -1、可能なら \(2 \times \text{dist}(1, T)\) を出力します。

アルゴリズム

1. 隣接リストで無向グラフを構築する。
2. ダイクストラ法で、始点 \(1\) から各頂点への最短距離 dist を求める。
3. dist[T] が無限大（到達不能）なら -1 を出力する。
4. 到達可能なら 2 * dist[T] を出力する。

ダイクストラ法の流れ（概要）： - dist[1]=0、それ以外は十分大きい値（INF）で初期化。 - 「現時点で最短距離が確定していない頂点のうち、距離が最小のもの」を優先度付きキューで取り出し、そこから伸びる辺で緩和（距離更新）する。

計算量

• 時間計算量: \(O((N+M)\log N)\)（優先度付きキューを使うダイクストラ法）
• 空間計算量: \(O(N+M)\)（隣接リストと距離配列）

実装のポイント

• 辺の重み \(C_i\) は最大 \(10^9\)、経路長は大きくなり得るため、INF は \(10^{30}\) のような十分大きい値にします。

• 入力サイズが大きいので sys.stdin.buffer.read() で高速に読み込みます。

• ダイクストラ法では、優先度付きキューから取り出した距離 d が dist[v] と一致しない場合（古い情報）は無視するのが定石です。

  ソースコード

import sys
import heapq

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

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    it = iter(data)
    N = next(it)
    M = next(it)
    T = next(it)

    g = [[] for _ in range(N + 1)]
    for _ in range(M):
        a = next(it); b = next(it); c = next(it)
        g[a].append((b, c))
        g[b].append((a, c))

    dist = dijkstra(N, g, 1)
    if dist[T] >= 10**30:
        print(-1)
    else:
        print(dist[T] * 2)

if __name__ == "__main__":
    main()

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