Overview

This is a problem where you need to find the shortest time to visit specified checkpoints in order on a given graph, and then move to the goal.

Analysis

At first glance, this problem appears to simply require computing the shortest distances between all pairs of vertices and then moving in the specified order. However, since the number of vertices \(N\) can be as large as \(5 \times 10^4\), we cannot use all-pairs shortest distances (e.g., Floyd–Warshall algorithm).

However, notice that the number of checkpoints to visit \(K\) is at most \(10\), which is very small. In other words, the shortest distances we actually need are only between at most \(12\) vertices in total: the start (vertex \(1\)), the checkpoints (at most \(10\)), and the goal (vertex \(N\)).

Therefore, it is sufficient to precompute the shortest distances from only these “necessary vertices” to all other vertices. This eliminates unnecessary computation and allows us to solve the problem efficiently.

Additionally, Dijkstra’s algorithm is well-suited for computing shortest distances from each vertex, and can be computed efficiently using a priority queue.

Algorithm

1. Build the graph as an adjacency list.
2. Create the list of necessary vertices: this is [1] + P[1..K] + [N].
3. For each vertex \(v\) in this list, use Dijkstra’s algorithm to compute the shortest distances dist[v][*] to all vertices.
4. Sum up the shortest distances between consecutively visited vertices to obtain the overall shortest time.
5. If any segment is unreachable (distance is \(\infty\)), output -1.

Example

For example, given the following input:

4 4 2
1 2 10
2 3 10
3 4 10
1 3 30
2 3

• The visit order is: 1 → 2 → 3 → 4
• Shortest distances:
  • 1→2: 10
  • 2→3: 10
  • 3→4: 10
• Total: 30

Complexity

• Time complexity: \(O(K \cdot (M \log N))\)
  • The number of necessary vertices is at most \(K+2\), and Dijkstra’s algorithm is run for each of them.
• Space complexity: \(O(N + M + K)\)
  • Memory used for the graph’s adjacency list, distance arrays, queues, etc.

Implementation Notes

• sys.stdin.read is used for fast input reading.

• By avoiding shortest distance computations for unnecessary vertices, the computational cost is significantly reduced.

• Pay attention to the usage of the priority queue (heapq) in the Dijkstra’s algorithm implementation.

  Source Code

import heapq
from collections import defaultdict
import sys

def dijkstra(graph, start, n):
    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, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                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 = defaultdict(list)
    
    for _ in range(M):
        u = int(data[idx]); idx += 1
        v = int(data[idx]); idx += 1
        t = int(data[idx]); idx += 1
        graph[u].append((v, t))
        graph[v].append((u, t))
    
    if K == 0:
        checkpoints = []
    else:
        checkpoints = list(map(int, data[idx:idx+K]))
        idx += K
    
    # チェックポイントリスト（1 → P1 → P2 → ... → PK → N）
    points = [1] + checkpoints + [N]
    L = len(points)
    
    # 各ノードから全点対最短距離を前計算（必要なノードのみ）
    required_nodes = list(set(points))
    dist_dict = {}
    
    for node in required_nodes:
        dist_dict[node] = dijkstra(graph, node, N)
    
    # 経路の総コストを計算
    total_time = 0
    for i in range(L - 1):
        s = points[i]
        t = points[i+1]
        d = dist_dict[s][t]
        if d == float('inf'):
            print(-1)
            return
        total_time += d
    
    print(total_time)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.