Overview

This problem asks for the minimum travel time to start from vertex 1, visit all \(K\) specified delivery destinations, and finally arrive at vertex \(N\). This is a variation of the Traveling Salesperson Problem (TSP). Given the constraint \(K \le 15\), we can solve it efficiently by combining Dijkstra’s algorithm and Bit DP (Dynamic Programming with bitmask).

Analysis

1. Naive Approach and Its Limitations

If \(K\) were very large, this problem would be NP-hard and difficult to solve quickly. There are \(K!\) possible orders to visit the delivery destinations. When \(K = 15\), \(15! \approx 1.3 \times 10^{12}\), so a brute-force search over all permutations will result in a Time Limit Exceeded (TLE) error.

2. Exploiting the Smallness of \(K\)

The only thing we need to optimize is the visiting order between specific locations: “vertex 1”, the “\(K\) delivery destinations \(C_1, \dots, C_K\)”, and “vertex \(N\)”. Therefore, we can divide and solve the problem in the following two steps:

1. Precompute the shortest distances between the required locations Since the number of vertices \(N \le 10^5\) is large, we cannot use the Floyd-Warshall algorithm (\(O(N^3)\)) to find the all-pairs shortest paths. However, if we fix a single starting vertex, we can find the shortest paths quickly in \(O((N + M) \log N)\) using Dijkstra’s algorithm. Since we only need the starting vertices to be “vertex 1” and the “\(K\) delivery destinations” (a total of \(K+1\) vertices), we can run Dijkstra’s algorithm \(K+1\) times to obtain all necessary shortest distances between these locations.

2. Optimize the route using Bit DP (Dynamic Programming) We apply dynamic programming with bitmask (Bit DP) where the states are “the set of delivery destinations visited so far” and “the current delivery destination”. By representing the set as a bitmask (binary number), we can keep the number of states to \(2^K \times K\). When \(K = 15\), the number of states is \(32768 \times 15 \approx 4.9 \times 10^5\), which is small enough to be processed extremely quickly.

---

Algorithm

Step 1: Calculating Shortest Distances with Dijkstra’s Algorithm

Run Dijkstra’s algorithm with each of the \(K+1\) vertices—”vertex 1” and the “\(K\) delivery destinations \(C_1, \dots, C_K\)“—as the starting point. This allows us to construct a table dist that stores the shortest distances between these locations: - dist[0][j]: The shortest distance from vertex 1 to each target (delivery destinations and vertex \(N\)) - dist[i][j] (\(1 \le i \le K\)): The shortest distance from delivery destination \(C_i\) to each target

Step 2: Optimizing the Route with Bit DP

Define the following DP table: - dp[mask][i]: The minimum travel time where the set of visited delivery destinations is represented by mask (bitmask) and the current location is delivery destination \(C_i\).

1. Initialization: Initialize all values in dp to \(\infty\) (a sufficiently large value). Since we start by moving from vertex 1 to the first delivery destination \(C_i\), initialize as follows: $\(dp[2^i][i] = \text{dist}[0][i+1] \quad (0 \le i < K)\)\( *(Note: Pay attention to the index alignment for `dist`: in `dist`, vertex 1 corresponds to `0`, and delivery destination \)C_i$ corresponds to i+1)*

2. Transitions: From the current state mask and current location \(i\), consider moving to a delivery destination \(j\) that has not been visited yet (the \(j\)-th bit of mask is 0). $\(dp[\text{mask} \cup \{j\}][j] = \min(dp[\text{mask} \cup \{j\}][j], dp[\text{mask}][i] + \text{dist}[i+1][j+1])\)$

3. Goal (Moving to vertex \(N\)): From the state where all delivery destinations have been visited (mask equals \(2^K - 1\)), we finally move to vertex \(N\). The answer we seek is the minimum of the following values: $\(\min_{0 \le i < K} (dp[2^K - 1][i] + \text{dist}[i+1][K+1])\)\( *(Note: In `dist`, vertex \)N$ corresponds to K+1)*

---

Complexity

• Time Complexity: \(O(K(M + N \log N) + 2^K \cdot K^2)\)

  • Dijkstra’s algorithm part: Since it is executed \(K+1\) times, the complexity is \(O(K (M + N \log N))\).
  • Bit DP part: Since the number of states is \(2^K \times K\) and the number of transitions from each state is \(K\), the complexity is \(O(2^K \cdot K^2)\).
  • When \(N = 10^5, M = 5 \times 10^4, \text{ and } K = 15\), the total number of operations is around \(3 \times 10^7\), which easily runs well within the time limit.

• Space Complexity: \(O(N + M + 2^K \cdot K)\)

  • We use \(O(N + M)\) memory to store the adjacency list and \(O(2^K \cdot K)\) memory for the DP table. This also easily fits within the memory limit.

---

Key Implementation Points

• Index Mapping: Converting the vertex indices to 0-indexed in your program helps reduce bugs. In this implementation, we organize the list of starting vertices sources and ending vertices targets used in Dijkstra’s algorithm as follows to make the index correspondence clear:

  • sources = [0] + C (length \(K+1\))
  • targets = [0] + C + [N - 1] (length \(K+2\))

• Bitwise Operations: To represent the set, we set the \(i\)-th bit (1 << i) to indicate that the \(i\)-th delivery destination has been visited.

  • Checking if not visited yet: not (mask & (1 << j))

  • Transitioning to a newly visited state: mask | (1 << j) Using these, we can write state transitions concisely and efficiently.

    Source Code

import sys
import heapq

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    K = int(input_data[2])
    
    adj = [[] for _ in range(N)]
    idx = 3
    for _ in range(M):
        u = int(input_data[idx]) - 1
        v = int(input_data[idx+1]) - 1
        w = int(input_data[idx+2])
        adj[u].append((v, w))
        adj[v].append((u, w))
        idx += 3
        
    C = []
    for _ in range(K):
        C.append(int(input_data[idx]) - 1)
        idx += 1
        
    sources = [0] + C
    targets = [0] + C + [N - 1]
    
    INF = 10**18
    dist = [[INF] * (K + 2) for _ in range(K + 1)]
    
    for i, s in enumerate(sources):
        d = [INF] * N
        d[s] = 0
        pq = [(0, s)]
        while pq:
            dist_u, u = heapq.heappop(pq)
            if dist_u > d[u]:
                continue
            for v, w in adj[u]:
                if d[v] > dist_u + w:
                    d[v] = dist_u + w
                    heapq.heappush(pq, (d[v], v))
        for j, t in enumerate(targets):
            dist[i][j] = d[t]
            
    dp = [[INF] * K for _ in range(1 << K)]
    
    for i in range(K):
        dp[1 << i][i] = dist[0][i+1]
        
    for mask in range(1, 1 << K):
        dp_mask = dp[mask]
        for i in range(K):
            d_curr = dp_mask[i]
            if d_curr == INF:
                continue
            dist_i = dist[i+1]
            for j in range(K):
                if not (mask & (1 << j)):
                    next_mask = mask | (1 << j)
                    new_d = d_curr + dist_i[j+1]
                    if dp[next_mask][j] > new_d:
                        dp[next_mask][j] = new_d
                        
    ans = INF
    full_mask = (1 << K) - 1
    dp_full = dp[full_mask]
    for i in range(K):
        val = dp_full[i] + dist[i+1][K+1]
        if val < ans:
            ans = val
            
    print(ans)

if __name__ == '__main__':
    solve()

---

This editorial was generated by gemini-3.5-flash-high.