概要

指定されたチェックポイントを決められた順番で通過してゴールする必要があるので、各区間（連続する2点間）の最短距離を足し合わせたものが全体の最小時間になる。

考察

この問題では通るべき順番が固定で、訪問順は
\(1 \rightarrow P_1 \rightarrow P_2 \rightarrow \cdots \rightarrow P_K \rightarrow N\)
と決まっています。

ここで重要なのは次の観察です：

• 全体の移動は上の順番の区間の連結で表せる。
• 例えば \(P_i\) に到着した後は、次に \(P_{i+1}\) に行かなければならないので、
  「\(P_i\) から \(P_{i+1}\) までの移動」だけを考えればよい。
• したがって、全体の最小時間は
  \(dist(1,P_1) + dist(P_1,P_2) + \cdots + dist(P_K,N)\)
  で求まる（各 \(dist(a,b)\) はグラフ上の最短距離）。

もしある区間 \(a \rightarrow b\) が到達不能なら、その時点で全体も到達不能なので答えは -1 です。

素朴な方法がダメな理由

全経路を探索して「順番通りにチェックポイントを踏む経路」を探すのは、分岐が多く経路数が爆発するため現実的ではありません（TLEの原因）。

そこで「各区間の最短距離」だけに分解し、最短経路問題として解きます。

アルゴリズム

各区間ごとにダイクストラ法で最短距離を求めて足し合わせます。

1. 入力から無向重み付きグラフを隣接リストで作る。
2. 訪問列 seq = [1] + P + [N] を作る。
3. 連続するペア \((seq[i], seq[i+1])\) ごとに：
   • ダイクストラ法で src -> dst の最短距離を求める。
   • 到達不能なら -1 を出力して終了。
   • 到達可能なら答えに加算。
4. 合計を出力。

実装では、ダイクストラ中に目的地 dst が優先度付きキューから取り出された時点で、その距離が確定最短なのでそこで打ち切りできます（高速化）。

計算量

• 時間計算量: \(O\big((K+1)\, M \log N\big)\)
  （区間は \(K+1 \le 11\) 個なので、実質的にダイクストラを最大11回）
• 空間計算量: \(O(N+M)\)
  （隣接リストと距離配列、ヒープ）

実装のポイント

• 到達不能判定：ダイクストラの結果が十分大きい（INF）なら -1。

• ヒープの古い要素の無視：d != dist[v] のときはスキップ（典型テクニック）。

• 早期終了：v == dst になったら即 return（その時点で最短距離確定）。

• src == dst の場合は距離 \(0\)（区間の両端が同じ可能性に備える）。

  ソースコード

import sys
import heapq

def dijkstra_to_target(g, n, src, dst):
    if src == dst:
        return 0
    INF = 10**30
    dist = [INF] * (n + 1)
    dist[src] = 0
    hq = [(0, src)]
    heappop = heapq.heappop
    heappush = heapq.heappush

    while hq:
        d, v = heappop(hq)
        if d != dist[v]:
            continue
        if v == dst:
            return d
        for to, w in g[v]:
            nd = d + w
            if nd < dist[to]:
                dist[to] = nd
                heappush(hq, (nd, to))
    return INF

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    it = 0
    N, M, K = data[it], data[it + 1], data[it + 2]
    it += 3

    g = [[] for _ in range(N + 1)]
    for _ in range(M):
        u, v, t = data[it], data[it + 1], data[it + 2]
        it += 3
        g[u].append((v, t))
        g[v].append((u, t))

    P = data[it:it + K]
    seq = [1] + P + [N]

    INF = 10**30
    ans = 0
    for a, b in zip(seq, seq[1:]):
        d = dijkstra_to_target(g, N, a, b)
        if d >= INF:
            print(-1)
            return
        ans += d

    print(ans)

if __name__ == "__main__":
    main()

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