概要

地点 \(S\) から出発し、荷物がある地点 \(G\) を経由して、目的地 \(T\) まで移動する際の最小時間を求める問題です。この問題は、グラフにおける「最短経路問題」に帰着できます。

考察

高橋君の移動は、以下の2つのフェーズに分けることができます。 1. 地点 \(S\) から地点 \(G\) への移動（荷物を取りに行く） 2. 地点 \(G\) から地点 \(T\) への移動（荷物を届ける）

全体の移動時間は、それぞれのフェーズにかかる時間の和になります。最短時間を求めるためには、「\(S\) から \(G\) への最短距離」と「\(G\) から \(T\) への最短距離」を求めればよいことが分かります。

ここで、道路は双方向に通行可能（無向グラフ）であるという点に注目します。無向グラフでは \(S\) から \(G\) への最短距離は、\(G\) から \(S\) への最短距離と等しくなります。したがって、地点 \(G\) を始点としてダイクストラ法を1回実行するだけで、地点 \(S\) への距離と地点 \(T\) への距離を同時に求めることができ、非常に効率的です。

もし \(G\) から \(S\)、あるいは \(G\) から \(T\) への経路が存在しない（距離が無限大のまま）場合は、条件を満たす移動が不可能であるため \(-1\) を出力します。

アルゴリズム

この問題は、負の重みがないグラフにおける単一始点最短経路問題を解くダイクストラ法を用いて解きます。

1. 地点 \(1\) から \(N\) までの隣接リストを作成し、各道路の情報を格納します。
2. 地点 \(G\) を始点としてダイクストラ法を開始します。
   • 優先度付きキュー（heapq）を用意し、(コスト 0, 地点 G) を追加します。
   • 各地点への最短距離を保持する配列 dist を無限大（inf）で初期化し、dist[G] = 0 とします。
   • キューから最小コストの地点を取り出し、隣接する地点のスコアを更新していく処理を繰り返します。
3. 計算された dist[S] と dist[T] を確認します。
   • どちらかが inf であれば、\(-1\) を出力します。
   • そうでなければ、dist[S] + dist[T] を出力します。

計算量

• 時間計算量: \(O((N + M) \log N)\)
  • ダイクストラ法において、各エッジの更新と優先度付きキューへの操作が発生するためです。\(N=10^5, M=1.5 \times 10^5\) の制約下では、この計算量で十分に実行時間制限内に収まります。
• 空間計算量: \(O(N + M)\)
  • グラフを保持するための隣接リストと、距離を保持する配列のメモリが必要です。

実装のポイント

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

• 優先度付きキュー: Python の heapq モジュールは最小ヒープを提供しているため、ダイクストラ法を簡単に実装できます。

• 到達不能の判定: 最短距離を格納する配列を十分大きな値（float('inf') など）で初期化し、最終的な値がそのままであれば「到達不能」と判断します。

  ソースコード

import heapq
import sys

def solve():
    # 入力を一度に読み込み、高速化を図る
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 地点数, M: 道路数, S: スタート地点, G: 荷物地点, T: ゴール地点
    N = int(input_data[0])
    M = int(input_data[1])
    S = int(input_data[2])
    G = int(input_data[3])
    T = int(input_data[4])
    
    # 隣接リストの構築
    adj = [[] for _ in range(N + 1)]
    ptr = 5
    for _ in range(M):
        u = int(input_data[ptr])
        v = int(input_data[ptr+1])
        c = int(input_data[ptr+2])
        adj[u].append((v, c))
        adj[v].append((u, c))
        ptr += 3
        
    # ダイクストラ法
    # 地点 G から全地点への最短距離を求めることで、dist(S, G) と dist(G, T) を一度に得る
    def dijkstra(start_node):
        distances = [float('inf')] * (N + 1)
        distances[start_node] = 0
        pq = [(0, start_node)] # (コスト, 現在の地点)
        
        while pq:
            current_dist, u = heapq.heappop(pq)
            
            # すでに確定している最短経路より長い場合はスキップ
            if current_dist > distances[u]:
                continue
            
            for v, weight in adj[u]:
                distance = current_dist + weight
                
                # より短い経路が見つかった場合、更新してキューに追加
                if distance < distances[v]:
                    distances[v] = distance
                    heapq.heappush(pq, (distance, v))
        return distances

    # 地点 G からの最短距離を計算
    dist_from_g = dijkstra(G)
    
    # S から G への距離と G から T への距離を取得
    # 無向グラフのため dist(S, G) == dist(G, S)
    d_gs = dist_from_g[S]
    d_gt = dist_from_g[T]
    
    # 到達可能か判定し、結果を出力
    if d_gs == float('inf') or d_gt == float('inf'):
        print("-1")
    else:
        # 必要な最小時間は dist(S, G) + dist(G, T)
        print(d_gs + d_gt)

if __name__ == "__main__":
    solve()

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