概要

地点 \(1\) から出発し、必ず地点 \(K\) を経由して地点 \(N\) へ行く最短時間を、重み付き無向グラフの最短経路問題として求めます。

考察

この問題のポイントは「必ず \(K\) を通る」という条件です。
\(1 \to N\) の最短経路をそのまま求めても、経路が \(K\) を通るとは限りません。

ここで重要な観察は次の通りです。

• \(1\) から \(N\) まで、途中で必ず \(K\) を通る任意の経路は
  「\(1 \to K\) の部分」と「\(K \to N\) の部分」に分けられる。
• したがって、求める答えは
  $\( \text{dist}(1,K) + \text{dist}(K,N) \)$ になります（それぞれ最短で行けば、全体としても最短）。

素朴に「\(1\) からの最短経路を全部試して、\(K\) を通るものだけ選ぶ」などをやると、経路数が膨大で現実的ではありません。また、\(N,M \le 2\times 10^5\) なので、各頂点から最短距離を何度も計算するような解法も間に合いません。

そこで、 - \(1\) を始点にダイクストラ法で全点への最短距離を求めて \(\text{dist}(1, \cdot)\) を得る - \(K\) を始点にもう一度ダイクストラ法で全点への最短距離を求めて \(\text{dist}(K, \cdot)\) を得る

とすれば、必要な \(\text{dist}(1,K)\) と \(\text{dist}(K,N)\) が一発で手に入ります。
どちらかが到達不可能なら、当然 \(1 \to K \to N\) も不可能なので -1 を出力します。

アルゴリズム

1. 隣接リストで無向グラフを構築する（各道路 \((u,v,c)\) を両方向に追加）。
2. ダイクストラ法を 2 回実行する。
   • 1回目：始点 \(1\) からの最短距離配列 dist1 を得る。
   • 2回目：始点 \(K\) からの最短距離配列 distK を得る。
3. dist1[K] または distK[N] が INF（到達不能）なら -1。
4. そうでなければ dist1[K] + distK[N] を出力。

ダイクストラ法を使う理由は、道路の所要時間 \(C_i\) がすべて正（\(C_i \ge 1\)）であり、重み付き最短経路を効率よく求められるからです。

計算量

• 時間計算量: \(O((N+M)\log N)\) を2回なので \(O((N+M)\log N)\)
• 空間計算量: 隣接リストと距離配列などで \(O(N+M)\)

実装のポイント

• INF を十分大きく：距離は最大で \(10^9\) が多数回足されうるので、10**30 のような大きい値を使います。

• 優先度付きキューの「古い情報」を捨てる：if d != dist[v]: continue を入れることで、更新前の距離で取り出された要素を無視し、計算量を保ちます。

• 無向グラフなので両方向に追加：graph[u].append((v,c)) と graph[v].append((u,c)) を忘れないようにします。

  ソースコード

import sys
import heapq

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

def main():
    input = sys.stdin.buffer.readline
    N, M, K = map(int, input().split())
    graph = [[] for _ in range(N + 1)]
    for _ in range(M):
        u, v, c = map(int, input().split())
        graph[u].append((v, c))
        graph[v].append((u, c))

    dist1 = dijkstra(1, graph, N)
    distK = dijkstra(K, graph, N)

    INF = 10**30
    if dist1[K] >= INF or distK[N] >= INF:
        print(-1)
    else:
        print(dist1[K] + distK[N])

if __name__ == "__main__":
    main()

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