概要

この問題は、重み付き無向グラフにおいて、拠点 \(1\) から拠点 \(T\) を経由して再び拠点 \(1\) に戻るまでの最短経路を求める問題です。

考察

最短経路問題を解くにあたって、以下の重要な性質に注目します。

1. 往路と復路の独立性 高橋君の移動は「拠点 \(1 \to T\)」という往路と、「拠点 \(T \to 1\)」という復路に分けられます。全体の時間を最小にするには、往路と復路のそれぞれで最短時間を達成すればよいことになります。

2. 無向グラフの対称性 この問題の道路は無向グラフ（双方向に移動可能でコストが同じ）です。無向グラフにおいて「地点 \(A\) から地点 \(B\) への最短距離」と「地点 \(B\) から地点 \(A\) への最短距離」は必ず一致します。 したがって、求める最小合計時間は以下のようになります。 $\((\text{拠点 } 1 \text{ から } T \text{ への最短距離}) \times 2\)$

3. 最短経路の探索 拠点の数 \(N\) が最大 \(10^5\)、道路の数 \(M\) が最大 \(2 \times 10^5\) と大きいため、効率的な最短経路アルゴリズムが必要です。エッジの重みが正であるため、ダイクストラ法を用いるのが最適です。

もしダイクストラ法の結果、拠点 \(T\) までの距離が無限大（到達不能）であれば、往復することも不可能なので -1 を出力します。

アルゴリズム

ダイクストラ法（優先度付きキューを使用）を用いて解きます。

1. グラフを隣接リスト形式で保持します。
2. 距離配列 dist を無限大で初期化し、出発点である dist[1] = 0 とします。
3. 優先度付きキューに (距離 0, 拠点 1) を追加します。
4. キューが空になるまで以下の操作を繰り返します：
   • 最も距離が短い拠点 \(u\) を取り出す。
   • すでにより短い距離で確定している場合はスキップする。
   • 拠点 \(u\) に隣接する各拠点 \(v\) について、拠点 \(u\) を経由したほうが早く着けるなら dist[v] を更新し、キューに加える。
   • （効率化のため、拠点 \(T\) の最短距離が確定した時点で探索を終了しても構いません）
5. dist[T] が更新されていれば dist[T] * 2 を出力し、そうでなければ -1 を出力します。

計算量

• 時間計算量: \(O(M \log N)\) ダイクストラ法において、各エッジを最大1回ずつ調べ、優先度付きキューの操作に \(O(\log N)\) かかるためです。
• 空間計算量: \(O(N + M)\) 隣接リストおよび距離配列を保持するために必要なメモリ量です。

実装のポイント

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

• 到達不能判定: 距離配列の初期値を非常に大きな値（float('inf') など）にしておき、最終的な値がそのままであれば到達不能と判断します。

• オーバーフロー: 答えが \(2 \times 10^{14}\) 程度になる可能性がありますが、Pythonは自動的に多倍長整数を扱うため、特に対策は不要です。他の言語（C++など）では long long 型を使用する必要があります。

  ソースコード

import heapq
import sys

def solve():
    # 標準入力から全てのデータを読み込み、空白で分割してリストにする
    # 大規模な入力に対して高速に動作させるための手法
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    it = iter(input_data)
    
    # N: 拠点の数, M: 道路の数, T: 訪問すべき拠点
    try:
        N = int(next(it))
        M = int(next(it))
        T = int(next(it))
    except StopIteration:
        return
    
    # 隣接リストの構築
    adj = [[] for _ in range(N + 1)]
    for _ in range(M):
        try:
            u = int(next(it))
            v = int(next(it))
            w = int(next(it))
            # 無向グラフなので両方向に追加
            adj[u].append((v, w))
            adj[v].append((u, w))
        except StopIteration:
            break
            
    # ダイクストラ法による最短経路探索
    # dist[i] は拠点1から拠点iまでの最短距離を保持する
    inf = float('inf')
    dist = [inf] * (N + 1)
    dist[1] = 0
    
    # 優先度付きキュー (現在の距離, 拠点番号)
    pq = [(0, 1)]
    
    while pq:
        d, u = heapq.heappop(pq)
        
        # すでに確定している距離より大きい場合はスキップ
        if d > dist[u]:
            continue
        
        # 目的の拠点 T に到達した時点で最短距離が確定するため終了可能
        if u == T:
            break
            
        # 隣接する拠点を探索
        for v, w in adj[u]:
            new_dist = d + w
            if new_dist < dist[v]:
                dist[v] = new_dist
                heapq.heappush(pq, (new_dist, v))
                
    # 拠点 T に到達できない場合
    if dist[T] == inf:
        print("-1")
    else:
        # 往復の最小時間は、行き(1からT)と帰り(Tから1)の最短距離の合計
        # 無向グラフにおいて最短経路は往路・復路で等しいため、2倍の値を出力する
        print(dist[T] * 2)

if __name__ == "__main__":
    solve()

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