概要

配達先 \(K(\le 15)\) 個を好きな順で全て訪れ、出発点 \(S\) に戻る最小コストを求めます。グラフは有向で、同じ道路・地点を何度通ってもよい（通るたびにコスト加算）問題です。

考察

• 通過回数の制限がないため、「最短経路で移動できる区間は常に最短で移動してよい」という性質があります。
  つまり、最適な巡回は「\(S\) と配達先たちの間を、最短距離の値でつないだ巡回」として考えられます。
• 素朴に「実際の経路（頂点列）を直接探索」すると、途中の寄り道や繰り返しが無限にあり得て探索空間が爆発します。また、配達先の訪問順全探索は \(K!\) で \(K=15\) では間に合いません。
• そこで次の 2 段階に分けます。
  1. 重要地点（\(S\) と \(T_1..T_K\)）間の最短距離を前計算する
     
  2. 重要地点だけからなる「巡回セールスマン問題（TSP）」をビットDPで解く
     
• もし重要地点間に到達不能（距離が \(\infty\)）があれば、その遷移は使えません。最終的に全配達先訪問＋\(S\)帰還ができない場合は -1 になります。

アルゴリズム

1. 重要地点を列挙
   \(imps = [S, T_1, \dots, T_K]\)（長さ \(K+1\)）。

2. ダイクストラで最短距離の前計算
   各重要地点 \(imps[i]\) を始点にダイクストラを行い、全頂点への最短距離を求めます。
   そこから重要地点同士の距離だけ抜き出して
   \(impdist[i][j] = dist(imps[i] \to imps[j])\)
   を作ります（サイズ \((K+1)\times(K+1)\)）。

3. ビットDPで「訪問順の最適化」
   配達先は \(K\) 個なので、集合をビットマスク \(mask(0..2^K-1)\) で表します。

   • \(dp[mask][i]\)：配達先集合 \(mask\) を訪問済みで、最後に \(T_i\) にいるときの最小コスト
     
   • 初期化：\(dp[1<<i][i] = impdist[S][T_i]\)
   • 遷移：未訪問の配達先 \(T_j\) を次に訪れる
     \(dp[mask \cup \{j\}][j] = \min(dp[mask][i] + impdist[T_i][T_j])\)
   • 答え：全訪問 \(full=(1<<K)-1\) について
     \(\min_i \{ dp[full][i] + impdist[T_i][S] \}\)
     （最後にどの配達先で終わっても、\(S\) に戻る）

4. 到達不能の扱い
   距離が \(\infty\) の区間は遷移できないため、最終答えも更新されなければ -1 を出力します。

計算量

• 時間計算量:
  ダイクストラを \(K+1\) 回行うので \(O\big((K+1)(M\log N)\big)\)、
  ビットDPが \(O(K^2 2^K)\)。
  よって全体で \(O\big((K+1)(M\log N) + K^2 2^K\big)\)
• 空間計算量:
  グラフ \(O(N+M)\)、距離表 \(O(K^2)\)、DP \(O(K2^K)\) なので
  \(O(N+M+K2^K)\)

実装のポイント

• 有向グラフなので、ダイクストラは「出辺」だけを辿ります（逆向きには進めない点に注意）。

• \(INF\) を十分大きく（例：\(10^{30}\)）して「到達不能」を表現します。

• DP 遷移は「未訪問ビットだけを列挙」すると無駄が減ります（コードでは rem をビット操作で走査）。

• 最後の「\(S\) に戻る」コスト（\(impdist[T_i][S]\)）を忘れずに加算して最小を取ります。

  ソースコード

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()

この解説は gpt-5.2-high によって生成されました。