Overview

Since you must pass through the specified checkpoints in a fixed order and reach the goal, the overall minimum time is the sum of shortest distances for each segment (between consecutive pairs of points).

Analysis

In this problem, the visiting order is fixed: \(1 \rightarrow P_1 \rightarrow P_2 \rightarrow \cdots \rightarrow P_K \rightarrow N\)

The key observation is as follows:

• The entire journey can be expressed as a concatenation of segments in the above order.
• For example, after arriving at \(P_i\), you must go to \(P_{i+1}\) next, so you only need to consider “the movement from \(P_i\) to \(P_{i+1}\).”
• Therefore, the overall minimum time is: \(dist(1,P_1) + dist(P_1,P_2) + \cdots + dist(P_K,N)\) where each \(dist(a,b)\) is the shortest distance on the graph.

If any segment \(a \rightarrow b\) is unreachable, then the entire journey is also unreachable, so the answer is -1.

Why a Naive Approach Fails

Exploring all paths to find one that visits checkpoints in the correct order is impractical because the number of branches is large and the number of paths explodes (causing TLE).

Instead, we decompose the problem into “shortest distance for each segment” and solve it as a shortest path problem.

Algorithm

We compute the shortest distance for each segment using Dijkstra’s algorithm and sum them up.

1. Build an undirected weighted graph as an adjacency list from the input.
2. Create the visit sequence seq = [1] + P + [N].
3. For each consecutive pair \((seq[i], seq[i+1])\):
   • Compute the shortest distance from src to dst using Dijkstra’s algorithm.
   • If unreachable, output -1 and terminate.
   • If reachable, add the distance to the answer.
4. Output the total.

In the implementation, once the destination dst is extracted from the priority queue during Dijkstra’s algorithm, its shortest distance is finalized, so we can terminate early at that point (optimization).

Complexity

• Time complexity: \(O\big((K+1)\, M \log N\big)\) (There are at most \(K+1 \le 11\) segments, so Dijkstra is run at most 11 times)
• Space complexity: \(O(N+M)\) (Adjacency list, distance array, and heap)

Implementation Notes

• Unreachability check: If the result of Dijkstra is sufficiently large (INF), output -1.

• Ignoring stale heap entries: Skip when d != dist[v] (a standard technique).

• Early termination: Return immediately when v == dst (the shortest distance is finalized at that point).

• When src == dst, the distance is \(0\) (to handle the case where both endpoints of a segment are the same).

  Source Code

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()

---

This editorial was generated by gpt-5.2-high.