概要

拠点1から拠点Tへ行って戻ってくる最短時間を求める問題で、往復経路は「行きの最短経路 × 2」で計算できます。

考察

重要な気づき

この問題のポイントは「往復」という点です。

• 行き: 拠点1 → 拠点T の最短経路
• 帰り: 拠点T → 拠点1 の最短経路

道路は双方向に同じ時間で通れるため、「行きの最短距離」と「帰りの最短距離」は等しくなります。

具体例で考える

例えば、以下のようなグラフを考えます：

拠点1 ---(5分)--- 拠点2 ---(3分)--- 拠点3(T)

• 1 → 3 の最短距離: 5 + 3 = 8分
• 3 → 1 の最短距離: 3 + 5 = 8分（同じ経路を逆に辿る）
• 往復の最短時間: 8 × 2 = 16分

なぜ往路と復路で別の経路を考えなくてよいか

無向グラフでは、任意の2点間の最短距離は行きも帰りも同じです。したがって、往路と復路で異なる経路を取ったとしても、合計時間が短くなることはありません。最短経路を往復するのが最適解となります。

アルゴリズム

1. グラフの構築: 入力からグラフを隣接リスト形式で構築する
2. ダイクストラ法: 拠点1を始点として、全頂点への最短距離を計算する
3. 答えの計算:
   • 拠点1から拠点Tへの最短距離 \(d\) を取得
   • \(d\) が無限大（到達不可能）なら -1 を出力
   • そうでなければ \(2 \times d\) を出力

ダイクストラ法の動作

ダイクストラ法は、始点から各頂点への最短距離を効率的に求めるアルゴリズムです。

1. 始点の距離を0、他の頂点の距離を∞に初期化
2. 優先度付きキュー（最小ヒープ）を使い、距離が最小の頂点から順に処理
3. 各頂点から隣接頂点へ移動したときの距離を更新（より短ければ）
4. 全頂点を処理するまで繰り返す

計算量

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

  • ダイクストラ法の計算量
  • 各頂点は最大1回処理され、各辺について優先度付きキューへの操作（\(O(\log N)\)）が行われる

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

  • グラフの隣接リスト: \(O(M)\)
  • 距離配列: \(O(N)\)
  • 優先度付きキュー: 最大 \(O(M)\)

実装のポイント

1. オーバーフロー対策: 距離の初期値には float('inf') を使用し、到達不可能な状態を表現

2. 既訪問頂点のスキップ:

   if d > dist[u]:
      continue
   

   同じ頂点が複数回キューに入ることがあるため、古い情報はスキップする

3. 1-indexed への対応:

   dist = [float('inf')] * (n + 1)
   

   拠点番号が1から始まるため、配列サイズを \(N+1\) にしている

4. 到達不可能の判定: dist_1_to_T == float('inf') で拠点Tに到達できない場合を検出し、-1 を出力

   ソースコード

import heapq
from collections import defaultdict

def dijkstra(graph, start, n):
    dist = [float('inf')] * (n + 1)
    dist[start] = 0
    pq = [(0, start)]
    
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))
    
    return dist

def main():
    N, M, T = map(int, input().split())
    
    graph = defaultdict(list)
    for _ in range(M):
        a, b, c = map(int, input().split())
        graph[a].append((b, c))
        graph[b].append((a, c))
    
    # 拠点1からの最短距離
    dist_from_1 = dijkstra(graph, 1, N)
    
    # 拠点1からTへの最短距離
    dist_1_to_T = dist_from_1[T]
    
    # 往復なので、1→T→1 の最短距離は 2 * dist(1, T)
    if dist_1_to_T == float('inf'):
        print(-1)
    else:
        print(2 * dist_1_to_T)

if __name__ == "__main__":
    main()

---

この解説は claude4.5opus によって生成されました。