概要

配送センター（地点 \(1\)）から中継拠点（地点 \(K\)）を経由して最終目的地（地点 \(N\)）へ向かう最短時間を求める問題です。

考察

この問題は、単純に「全ての経路を試す」と非常に多くの組み合わせが存在するため、現実的ではありません。また、負のコストがないグラフなので、ダイクストラ法のような最短経路アルゴリズムが有効です。

重要な観察は、「地点 \(1\) → 地点 \(K\) → 地点 \(N\)」という経路における最短時間は、
「地点 \(1\) から地点 \(K\) までの最短距離」と「地点 \(K\) から地点 \(N\) までの最短距離」の和であるということです。

つまり、2回のダイクストラ法を用いれば、全体の最短時間を求めることができます。

もし地点 \(1\) から地点 \(K\) に到達できない場合や、地点 \(K\) から地点 \(N\) に到達できない場合は、配達が不可能なので -1 を出力します。

アルゴリズム

1. グラフを隣接リスト形式で構築します。
2. ダイクストラ法を用いて以下の2つの最短距離を計算します：
   • 地点 \(1\) からの各頂点への最短距離（dist_from_1）
   • 地点 \(K\) からの各頂点への最短距離（dist_from_K）
3. 最終的に、dist_from_1[K] + dist_from_K[N] の値を答えとします。
4. どちらか一方でも到達不能（距離が無限大）なら -1 を出力します。

ダイクストラ法は優先度付きキュー（ヒープ）を使って効率的に最小コストの頂点を取り出しながら探索を行います。

計算量

• 時間計算量: \(O((N + M) \log N)\)
  （ダイクストラ法を2回実行するため、それぞれ \(O((N + M) \log N)\)）
• 空間計算量: \(O(N + M)\)
  （グラフの隣接リスト表現と距離配列による）

実装のポイント

• グラフは無向グラフなので、入力の道路情報から両方向に辺を追加すること。
• ダイクストラ法の初期化では、スタート地点の距離を 0 に設定し、他の頂点の距離を inf にしておくこと。
• 結果が inf かどうかで到達可能性を判定できるので、比較には十分大きな値ではなく float('inf') をそのまま使うのが安全。

## ソースコード

```python
import heapq
import sys

def dijkstra(n, graph, start):
    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, cost in graph[u]:
            if dist[u] + cost < dist[v]:
                dist[v] = dist[u] + cost
                heapq.heappush(pq, (dist[v], v))
    
    return dist

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1
    K = int(data[idx]); idx += 1
    
    graph = [[] for _ in range(N + 1)]
    
    for _ in range(M):
        u = int(data[idx]); idx += 1
        v = int(data[idx]); idx += 1
        c = int(data[idx]); idx += 1
        graph[u].append((v, c))
        graph[v].append((u, c))
    
    dist_from_1 = dijkstra(N, graph, 1)
    dist_from_K = dijkstra(N, graph, K)
    
    total_time = dist_from_1[K] + dist_from_K[N]
    if total_time >= float('inf'):
        print(-1)
    else:
        print(total_time)

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。