Overview

We need to find the minimum cost to visit all \(K(\le 15)\) delivery destinations in any order and return to the starting point \(S\). The graph is directed, and the same roads and locations can be traversed multiple times (with costs added each time).

Key Observations

• Since there is no restriction on the number of times a location can be visited, the property “segments that can be traversed via shortest paths should always use shortest paths” holds.
  In other words, the optimal tour can be thought of as “a tour connecting \(S\) and the delivery destinations using shortest distance values.”
• Naively “directly searching the actual path (vertex sequence)” leads to an explosion in search space due to potentially infinite detours and repetitions. Also, brute-force enumeration of delivery destination visit orders is \(K!\), which is too slow for \(K=15\).
• Therefore, we split the problem into two stages:
  1. Precompute shortest distances between important locations (\(S\) and \(T_1..T_K\))
     
  2. Solve the “Traveling Salesman Problem (TSP)” on only the important locations using bitmask DP
     
• If any pair of important locations is unreachable (distance is \(\infty\)), that transition cannot be used. If visiting all delivery destinations and returning to \(S\) is impossible, output -1.

Algorithm

1. Enumerate important locations
   \(imps = [S, T_1, \dots, T_K]\) (length \(K+1\)).

2. Precompute shortest distances with Dijkstra
   Run Dijkstra from each important location \(imps[i]\) to compute shortest distances to all vertices.
   Then extract only the distances between important locations:
   \(impdist[i][j] = dist(imps[i] \to imps[j])\)
   (size \((K+1)\times(K+1)\)).

3. Bitmask DP for “optimizing visit order”
   Since there are \(K\) delivery destinations, represent the set with a bitmask \(mask(0..2^K-1)\).

   • \(dp[mask][i]\): minimum cost when the set of visited delivery destinations is \(mask\) and we are currently at \(T_i\)
     
   • Initialization: \(dp[1<<i][i] = impdist[S][T_i]\)
   • Transition: visit an unvisited delivery destination \(T_j\) next
     \(dp[mask \cup \{j\}][j] = \min(dp[mask][i] + impdist[T_i][T_j])\)
   • Answer: for the full visit mask \(full=(1<<K)-1\),
     \(\min_i \{ dp[full][i] + impdist[T_i][S] \}\)
     (regardless of which delivery destination we end at, we return to \(S\))

4. Handling unreachability
   Transitions with \(\infty\) distance cannot be taken, so if the final answer is never updated, output -1.

Complexity

• Time complexity:
  Running Dijkstra \(K+1\) times gives \(O\big((K+1)(M\log N)\big)\),
  and the bitmask DP is \(O(K^2 2^K)\).
  Overall: \(O\big((K+1)(M\log N) + K^2 2^K\big)\)
• Space complexity:
  Graph \(O(N+M)\), distance table \(O(K^2)\), DP \(O(K2^K)\), so
  \(O(N+M+K2^K)\)

Implementation Notes

• Since the graph is directed, Dijkstra only follows outgoing edges (be careful not to traverse edges in reverse).

• Set \(INF\) to a sufficiently large value (e.g., \(10^{30}\)) to represent “unreachable.”

• In the DP transition, enumerating “only unvisited bits” reduces unnecessary work (in the code, rem is scanned using bit operations).

• Don’t forget to add the “return to \(S\)” cost (\(impdist[T_i][S]\)) at the end and take the minimum.

  Source Code

import sys
import heapq

def main():
    it = iter(map(int, sys.stdin.buffer.read().split()))
    try:
        N = next(it)
    except StopIteration:
        return
    M = next(it)

    g = [[] for _ in range(N + 1)]
    for _ in range(M):
        u = next(it); v = next(it); w = next(it)
        g[u].append((v, w))

    S = next(it)
    K = next(it)
    T = [next(it) for _ in range(K)]

    INF = 10**30

    def dijkstra(src: int):
        dist = [INF] * (N + 1)
        dist[src] = 0
        hq = [(0, src)]
        while hq:
            d, u = heapq.heappop(hq)
            if d != dist[u]:
                continue
            for v, w in g[u]:
                nd = d + w
                if nd < dist[v]:
                    dist[v] = nd
                    heapq.heappush(hq, (nd, v))
        return dist

    imps = [S] + T
    L = K + 1
    impdist = [[INF] * L for _ in range(L)]
    for i, src in enumerate(imps):
        d = dijkstra(src)
        row = impdist[i]
        for j, dst in enumerate(imps):
            row[j] = d[dst]

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

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

    for mask in range(1 << K):
        row = dp[mask]
        rem0 = full ^ mask
        for i in range(K):
            cur = row[i]
            if cur >= INF:
                continue
            rem = rem0
            while rem:
                lb = rem & -rem
                j = lb.bit_length() - 1
                nd = cur + impdist[i + 1][j + 1]
                nm = mask | lb
                if nd < dp[nm][j]:
                    dp[nm][j] = nd
                rem -= lb

    ans = INF
    for i in range(K):
        cur = dp[full][i]
        back = impdist[i + 1][0]
        if cur < INF and back < INF:
            v = cur + back
            if v < ans:
                ans = v

    print(-1 if ans >= INF else ans)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.