Summary

This problem asks for the minimum travel time to start from vertex \(1\), visit all \(K\) specified delivery destinations, and then arrive at vertex \(N\). The order in which we visit the destinations can be chosen freely. This is a classic problem that combines the Traveling Salesperson Problem (TSP) with the shortest path problem.

Analysis

Important Observation 1: Order Optimization is Required

Since we can visit the destinations in any order, we need to consider all possible orders of visiting the \(K\) destinations. Naively trying all permutations would take \(O(K!)\) time, which for \(K = 15\) is \(15! \approx 1.3 \times 10^{12}\) and is far too slow to pass within the time limit.

Therefore, we can use bitDP (Dynamic Programming with Bitmask) to optimize the order in \(O(2^K \cdot K^2)\) time.

Important Observation 2: Only the Shortest Distances Between Locations Matter

Since we can freely pass through any locations other than the destinations along the way, and we can visit the same locations/roads multiple times, we can replace the travel costs of:

• “Vertex \(1\) \(\to\) some destination”
• “some destination \(\to\) another destination”
• “some destination \(\to\) Vertex \(N\)”

with the shortest path (shortest distance) on the graph. In other words, we can compress the original graph into a “complete graph consisting only of the important vertices (Vertex \(1\), each destination, and Vertex \(N\))” and solve the TSP on this compressed graph.

How to Calculate Distances

The required shortest distances are as follows:

• The distance from Vertex \(1\) to each destination \(C_i\)
• The distance from each destination \(C_i\) to another destination \(C_j\)
• The distance from each destination \(C_i\) to Vertex \(N\)

All of these can be obtained by running Dijkstra’s algorithm \(K\) times with each destination \(C_i\) as the starting point, plus running it \(1\) time with Vertex \(1\) as the starting point (since the roads are bidirectional, the distance from \(C_i\) to \(N\) can be obtained from the Dijkstra run starting from \(C_i\)).

Thus, we run Dijkstra’s algorithm a total of \(K + 1\) times.

Algorithm

Step 1: Precalculating Shortest Distances

• Run Dijkstra starting from Vertex \(1\) \(\to\) start_to[i] (distance from Vertex \(1\) to \(C_i\))
• Run Dijkstra starting from each \(C_i\) \(\to\)
  • dd[i][j] (distance from \(C_i\) to \(C_j\))
  • to_N[i] (distance from \(C_i\) to Vertex \(N\))

Step 2: bitDP

Let dp[mask][i] be the “minimum travel time from Vertex \(1\) when the set of destinations visited so far is represented by mask, and the last visited destination is \(i\)”.

Initialization: When the first destination to visit is \(i\): $\(dp[\{i\}][i] = \text{start\_to}[i]\)$

Transitions: When transitioning from state \((mask, i)\) to a destination \(j\) that has not been visited yet: $\(dp[mask \cup \{j\}][j] \leftarrow \min\big(dp[mask \cup \{j\}][j],\ dp[mask][i] + dd[i][j]\big)\)$

Answer: We take the minimum value over all possible last visited destinations \(i\) to go to Vertex \(N\) from the state full (\(=2^K - 1\)) where all destinations have been visited. $\(\text{ans} = \min_i \big(dp[full][i] + \text{to\_N}[i]\big)\)$

Complexity

• Running Dijkstra’s algorithm \(K + 1\) times: \(O\big((K+1)(M + N)\log N\big)\)
• bitDP: \(O(2^K \cdot K^2)\)

In total,

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

Since \(K \le 15\), we have \(2^K K^2 \approx 7.4 \times 10^6\), and the Dijkstra part is also fast enough to easily fit within the time limit.

Key Implementation Points

• Distances can become very large: \(W_i\) is up to \(10^9\), and since the path spans multiple destinations, the total distance requires a 64-bit integer. In Python, integers have arbitrary precision, so there is no need to worry about overflow, but in C++, you must use long long.

• Skipping invalid states: In the bitDP transitions, skipping cases where dp[mask][i] is INF (unreachable) or where \(i\) is not included in mask helps avoid redundant calculations.

• Fast I/O: Since \(N\) and \(M\) are large, reading the entire input at once using sys.stdin.buffer.read() is fast.

• Implement Dijkstra with a heap (priority queue): We use heapq and apply the standard technique of skipping the element if the popped distance is greater than the already recorded distance (i.e., outdated information).

  Source Code

import sys
import heapq

def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1
    K = int(data[idx]); idx += 1

    adj = [[] for _ in range(N + 1)]
    for _ in range(M):
        u = int(data[idx]); idx += 1
        v = int(data[idx]); idx += 1
        w = int(data[idx]); idx += 1
        adj[u].append((v, w))
        adj[v].append((u, w))

    C = [int(data[idx + i]) for i in range(K)]
    idx += K

    INF = float('inf')

    def dijkstra(start):
        dist = [INF] * (N + 1)
        dist[start] = 0
        h = [(0, start)]
        while h:
            d, u = heapq.heappop(h)
            if d > dist[u]:
                continue
            for v, w in adj[u]:
                nd = d + w
                if nd < dist[v]:
                    dist[v] = nd
                    heapq.heappush(h, (nd, v))
        return dist

    # distances from start node 1
    d_start = dijkstra(1)
    start_to = [d_start[C[i]] for i in range(K)]

    # distances from each delivery
    dd = [None] * K
    to_N = [0] * K
    delivery_dist = []
    for i in range(K):
        di = dijkstra(C[i])
        delivery_dist.append(di)
        to_N[i] = di[N]

    dd = [[delivery_dist[i][C[j]] for j in range(K)] for i in range(K)]

    full = (1 << K) - 1
    dp = [[INF] * K for _ in range(1 << K)]
    for i in range(K):
        dp[1 << i][i] = start_to[i]

    for mask in range(1 << K):
        row = dp[mask]
        for i in range(K):
            if not (mask >> i) & 1:
                continue
            cur = row[i]
            if cur == INF:
                continue
            ddi = dd[i]
            for j in range(K):
                if (mask >> j) & 1:
                    continue
                nd = cur + ddi[j]
                nm = mask | (1 << j)
                if nd < dp[nm][j]:
                    dp[nm][j] = nd

    ans = INF
    for i in range(K):
        v = dp[full][i] + to_N[i]
        if v < ans:
            ans = v

    print(ans)

main()

---

This editorial was generated by claude4.8opus-high.