Overview

We want to find the minimum time to start from location \(1\), visit all \(K\) specified delivery destinations, and then arrive at location \(N\).

Since \(K \leq 15\) is small, we can first find the “shortest distances between important locations” and then optimize the visiting order of the destinations using bitmask DP.

Analysis

We can visit the destinations in any order.
For example, if the destinations are \(C_1, C_2, C_3\), we can visit them in an order like this:

\[ 1 \to C_2 \to C_1 \to C_3 \to N \]

In this case, it is optimal to always use the shortest path for each segment.
In other words, the travel time for the above sequence can be calculated as:

\[ \operatorname{dist}(1, C_2) + \operatorname{dist}(C_2, C_1) + \operatorname{dist}(C_1, C_3) + \operatorname{dist}(C_3, N) \]

Therefore, we first need the shortest distances between the following “important locations”:

• Starting location \(1\)
• Destinations \(C_1, C_2, \dots, C_K\)
• Ending location \(N\)

There are only \(K+2\) important locations in total.

However, finding the shortest paths between all pairs of vertices using the Floyd-Warshall algorithm would take \(O(N^3)\) time, which is impossible since \(N \leq 10^5\).

On the other hand, since all edge weights are positive, we can use Dijkstra’s algorithm.
By running Dijkstra’s algorithm only from the important locations, we can efficiently find only the necessary distances.

After that, we can determine the visiting order of the destinations using bitmask DP.

Naively trying all permutations would result in \(K!\) possibilities.
When \(K=15\), \(15!\) is extremely large and will not run in time.

Therefore, by using a DP that manages the visited set with a bitmask, we can reduce the time complexity to \(O(2^K K^2)\).

Algorithm

We define the important locations as follows:

\[ P_0 = 1 \]

\[ P_i = C_i \quad (1 \leq i \leq K) \]

\[ P_{K+1} = N \]

1. Finding the Shortest Distances Between Important Locations

We run Dijkstra’s algorithm from each important location \(P_0, P_1, \dots, P_K\).

Note that we do not need to run Dijkstra’s algorithm from the ending location \(N = P_{K+1}\).
Since the roads are bidirectional, the distance

\[ \operatorname{dist}(C_i, N) \]

is already obtained from the results of running Dijkstra’s algorithm from \(C_i\).

In the code, pair_dist[a][b] is stored as:

\[ \text{the shortest distance from } P_a \text{ to } P_b \]

2. Determining the Visiting Order Using Bitmask DP

We define the DP state as follows:

\[ dp[mask][i] \]

is the minimum travel time from location \(1\), where:

• mask represents the set of already visited destinations.
• \(C_i\) is the last visited destination (the current location).

Here, mask is a \(K\)-bit integer.
For example, when \(K=4\), mask = 0101 (binary) means that \(C_0\) and \(C_2\) have been visited.

Initialization

The initial state corresponds to going directly from location \(1\) to \(C_i\):

\[ dp[1 << i][i] = \operatorname{dist}(1, C_i) \]

In the code, this is written as:

dp[1 << i][i] = pair_dist[0][i + 1]

Transitions

Suppose we are currently at \(C_i\), and we visit \(C_j\) (which has not been visited yet) next:

\[ dp[mask \cup \{j\}][j] = \min( dp[mask \cup \{j\}][j], dp[mask][i] + \operatorname{dist}(C_i, C_j) ) \]

In the code, this transition to the next destination is represented as:

nd = cur + d_from_i[j + 1]

Answer

Let full be the state where all destinations have been visited.

If the last visited destination is \(C_i\), we just need to go from there to location \(N\). Thus, the minimum value of:

\[ dp[full][i] + \operatorname{dist}(C_i, N) \]

over all \(i\) is the answer.

In the code, this is calculated as:

ans = INF
for i in range(K):
    val = dp[full][i] + pair_dist[i + 1][K + 1]
    ans = min(ans, val)

Complexity

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

We run Dijkstra’s algorithm \(K+1\) times.
The number of states in the bitmask DP is \(2^K K\), and for each state, we transition to the next destination, which takes \(O(2^K K^2)\) time in total.

Since \(K \leq 15\), the bitmask DP runs fast enough.

Implementation Points

In Dijkstra’s algorithm, although we need to find the distances to all vertices, we only care about the distances to the important locations.

In the code, we prepare important_idx to determine in \(O(1)\) time whether the popped vertex is an important location:

important_idx = [-1] * (N + 1)
for i, v in enumerate(important):
    important_idx[v] = i

Additionally, in Dijkstra’s algorithm, the shortest distance to a vertex is determined at the moment it is popped from the priority queue.
Therefore, once the distances to all important locations are determined, we can terminate the search early:

while hq and remain:

However, the worst-case complexity remains the same as standard Dijkstra’s algorithm.

Since the maximum distance can be quite large, we use a sufficiently large value like INF = 10**30.

Source Code

import sys
import heapq

def main():
    input = sys.stdin.buffer.readline

    N, M, K = map(int, input().split())
    graph = [[] for _ in range(N + 1)]

    for _ in range(M):
        u, v, w = map(int, input().split())
        graph[u].append((v, w))
        graph[v].append((u, w))

    C = list(map(int, input().split()))

    important = [1] + C + [N]
    L = K + 2

    important_idx = [-1] * (N + 1)
    for i, v in enumerate(important):
        important_idx[v] = i

    INF = 10**30

    def dijkstra(start):
        dist = [INF] * (N + 1)
        dist[start] = 0

        res = [INF] * L
        remain = L

        hq = [(0, start)]
        heappush = heapq.heappush
        heappop = heapq.heappop
        g = graph
        idx = important_idx

        while hq and remain:
            d, v = heappop(hq)
            if d != dist[v]:
                continue

            ii = idx[v]
            if ii != -1 and res[ii] == INF:
                res[ii] = d
                remain -= 1

            for to, w in g[v]:
                nd = d + w
                if nd < dist[to]:
                    dist[to] = nd
                    heappush(hq, (nd, to))

        return res

    pair_dist = [dijkstra(v) for v in important[:-1]]

    size = 1 << K
    full = size - 1

    dp = [[INF] * K for _ in range(size)]

    for i in range(K):
        dp[1 << i][i] = pair_dist[0][i + 1]

    for mask in range(size):
        row = dp[mask]
        rest = full ^ mask

        for i in range(K):
            cur = row[i]
            if cur == INF:
                continue

            d_from_i = pair_dist[i + 1]
            b = rest

            while b:
                lsb = b & -b
                j = lsb.bit_length() - 1
                nm = mask | lsb
                nd = cur + d_from_i[j + 1]

                if nd < dp[nm][j]:
                    dp[nm][j] = nd

                b -= lsb

    ans = INF
    for i in range(K):
        val = dp[full][i] + pair_dist[i + 1][K + 1]
        if val < ans:
            ans = val

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.