Overview

This problem asks us to find the minimum travel time starting from vertex \(1\), visiting all \(K\) specified delivery destinations, and arriving at vertex \(N\).

Analysis

Since the order of visiting the \(K\) destinations is arbitrary, there are \(K!\) possible orderings. Under the constraint \(K \leq 15\), \(15! \approx 1.3 \times 10^{12}\), which would result in TLE (Time Limit Exceeded) if we try all permutations.

However, we can significantly reduce the computational complexity by keeping track of the state as “the set of already visited destinations” and “the last visited destination”. This is a typical approach for the Traveling Salesperson Problem (TSP), and it can be solved in \(O(K^2 2^K)\) time using Bitmask DP.

Additionally, the shortest travel times between any pair of target nodes can be precomputed using Dijkstra’s algorithm, allowing for fast transitions in the DP.

Algorithm

1. Computing Shortest Distances Between Targets: We group the starting vertex (vertex \(1\)), the destination vertex (vertex \(N\)), and the delivery locations (\(C_1, \dots, C_K\)) together as a total of \(K+2\) target nodes. We run Dijkstra’s algorithm starting from each target node to find the shortest distances between all pairs of targets.

2. Searching for the Optimal Path using Bitmask DP:

   • Let dp[mask][i] be the minimum travel time when the set of visited destinations is represented by the bitmask mask and the last visited destination is the i-th one.
   • As the initial state, set the distances for moving directly from the starting vertex to each destination.
   • From each state, transition to an unvisited destination j and update the dp table.
   • Finally, the answer will be the minimum travel time to reach the destination vertex (vertex \(N\)) from the state where all destinations have been visited.

Complexity

• Time Complexity: \(O((K+2) M \log N + K^2 2^K)\) Since Dijkstra’s algorithm is run \(K+2\) times, it takes \(O((K+2) M \log N)\) time, and the Bitmask DP transitions take \(O(K^2 2^K)\) time. This is sufficiently fast under the constraints.
• Space Complexity: \(O(N + M + K^2)\) It consumes about \(O(N + M)\) memory for the graph’s adjacency list and Dijkstra’s algorithm arrays, and around \(O(K^2)\) memory for the distances between targets and the DP table.

Implementation Points

• To make it easier to manage the indices of the destinations, constructing the target list as [1, N] + C allows us to treat the starting vertex as index 0, the destination vertex as index 1, and each delivery location starting from index 2, which is very convenient.

• In the DP initialization, set the distances from the starting vertex (index 0) to each destination (index i + 2) as dp[1 << i][i] = dist[0][i + 2].

• After the DP transitions, find the minimum value by adding the distance to the final destination (index 1), dist[i + 2][1], from the state where all destinations have been visited (full_mask = (1 << K) - 1).

  Source Code

import sys
import heapq

def solve():
    input = sys.stdin.readline
    N, M, K = map(int, input().split())
    
    adj = [[] for _ in range(N + 1)]
    for _ in range(M):
        u, v, w = map(int, input().split())
        adj[u].append((v, w))
        adj[v].append((u, w))
        
    C = list(map(int, input().split()))
    # 始点(1), 終点(N), 届け先(C)
    targets = [1, N] + C
    T = len(targets)
    
    # 各targetからの最短距離を計算するためのDijkstra
    dist = [[0] * T for _ in range(T)]
    
    for start_idx in range(T):
        start_node = targets[start_idx]
        d = [10**18] * (N + 1)
        d[start_node] = 0
        pq = [(0, start_node)]
        while pq:
            cd, cn = heapq.heappop(pq)
            if cd > d[cn]:
                continue
            for nxt, w in adj[cn]:
                nd = cd + w
                if nd < d[nxt]:
                    d[nxt] = nd
                    heapq.heappush(pq, (nd, nxt))
        for end_idx in range(T):
            dist[start_idx][end_idx] = d[targets[end_idx]]
            
    # TSP DP
    # 始点: targets[0] (1)
    # 終点: targets[1] (N)
    # 届け先: targets[2] ~ targets[K+1] (C_1 ~ C_K)
    
    INF = 10**18
    dp = [[INF] * K for _ in range(1 << K)]
    
    # 初期化: 始点から各届け先への移動
    for i in range(K):
        dp[1 << i][i] = dist[0][i + 2]
        
    # DP遷移
    for mask in range(1, 1 << K):
        for i in range(K):
            if not (mask & (1 << i)):
                continue
            cur = dp[mask][i]
            if cur == INF:
                continue
            for j in range(K):
                if mask & (1 << j):
                    continue
                nxt_mask = mask | (1 << j)
                cost = cur + dist[i + 2][j + 2]
                if cost < dp[nxt_mask][j]:
                    dp[nxt_mask][j] = cost
                    
    # 最終状態から終点(N)への移動
    ans = INF
    full_mask = (1 << K) - 1
    for i in range(K):
        if dp[full_mask][i] != INF:
            cost = dp[full_mask][i] + dist[i + 2][1]
            if cost < ans:
                ans = cost
                
    print(ans)

if __name__ == '__main__':
    solve()

---

This editorial was generated by or-glm5.2-high.