概要

この問題は、営業所を出発してすべての配達先を巡回し、営業所に戻る最短経路を求める巡回セールスマン問題（TSP）の一種です。ただし、グラフのサイズが大きいため、すべてのノード間の最短距離を事前計算し、配達先のみを対象にTSPを解く必要があります。

考察

• グラフのサイズが最大\(N=10000\)ノード、\(M=20000\)辺と大きいため、すべてのノード間の最短距離を直接計算することはできません。
• しかし、配達先の数\(K\)は最大15と小さいため、営業所\(S\)と配達先\(D_j\)のみを対象とした部分グラフを考えることができます。
• まず、営業所\(S\)と各配達先\(D_j\)を始点としたダイクストラ法で、これらの点同士の最短距離を事前計算します。
• その後、営業所と配達先のみを頂点とする完全グラフ上で、巡回セールスマン問題（TSP）を動的計画法（bit DP）で解きます。

アルゴリズム

1. 事前計算: 営業所\(S\)とすべての配達先\(D_j\)を始点として、各点から全交差点への最短距離をダイクストラ法で計算します。これにより、\(S\)と\(D_j\)の間の最短距離\(dists[u][v]\)が得られます。
2. TSPの設定: 頂点集合を\(\{S, D_1, D_2, \ldots, D_K\}\)とし、辺の重みを事前計算した最短距離とします。この完全グラフ上で、\(S\)から出発してすべての頂点を訪問し\(S\)に戻る最短経路を求めます。
3. bit DP:
   • \(dp[mask][i]\): 訪問済み頂点集合が\(mask\)（ビットマスク）で、最後に訪問した頂点が\(i\)番目のときの最小コスト。
   • 初期状態: \(dp[1][0] = 0\)（営業所\(S\)を最初に訪問）。
   • 遷移: 未訪問の頂点\(j\)について、\(dp[new\_mask][j] = \min(dp[new\_mask][j], dp[mask][i] + dists[i][j])\)。
4. 答えの計算: すべての頂点を訪問した状態（\(mask = (1<<(K+1))-1\)）から、最後の頂点\(i\)から営業所\(S\)に戻るコスト\(dists[i][S]\)を加算し、最小値を求めます。

計算量

• 時間計算量: \(O((K+1) \cdot (M \log N) + O(2^{K+1} \cdot (K+1)^2)\)
  • ダイクストラ法を\(K+1\)回実行: \(O((K+1) \cdot (M \log N))\)
  • bit DP: \(O(2^{K+1} \cdot (K+1)^2)\)
• 空間計算量: \(O(N + M + 2^{K+1} \cdot (K+1))\)
  • グラフの表現: \(O(N + M)\)
  • 事前計算した距離テーブル: \(O((K+1) \cdot N)\)
  • DPテーブル: \(O(2^{K+1} \cdot (K+1))\)

実装のポイント

• ダイクストラ法では、各始点について最短距離を計算し、配列distsに保存します。

• 点のリストpointsには、営業所\(S\)を0番目に、配達先を1番目以降に格納します。

• bit DPでは、状態をビットマスクで管理し、未訪問の頂点への遷移をループで処理します。

• 大きな数値（\(10^{18}\)）で初期化し、オーバーフローを防ぎます。

  ソースコード

import heapq
import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        return
    
    it = iter(data)
    n = int(next(it)); m = int(next(it))
    graph = [[] for _ in range(n+1)]
    for _ in range(m):
        u = int(next(it)); v = int(next(it)); w = int(next(it))
        graph[u].append((v, w))
        graph[v].append((u, w))
    
    S = int(next(it)); K = int(next(it))
    Ds = [int(next(it)) for _ in range(K)]
    
    points = [S] + Ds
    dists = {}
    
    for start in points:
        dist = [10**18] * (n+1)
        dist[start] = 0
        heap = [(0, start)]
        while heap:
            d, u = heapq.heappop(heap)
            if d != dist[u]:
                continue
            for v, w in graph[u]:
                if dist[v] > d + w:
                    dist[v] = d + w
                    heapq.heappush(heap, (dist[v], v))
        dists[start] = dist
    
    size = K + 1
    dp = [[10**18] * size for _ in range(1 << size)]
    dp[1][0] = 0
    
    for mask in range(1 << size):
        for i in range(size):
            if dp[mask][i] == 10**18:
                continue
            for j in range(size):
                if mask & (1 << j):
                    continue
                new_mask = mask | (1 << j)
                u = points[i]
                v = points[j]
                cost = dists[u][v]
                if dp[new_mask][j] > dp[mask][i] + cost:
                    dp[new_mask][j] = dp[mask][i] + cost
    
    ans = 10**18
    full_mask = (1 << size) - 1
    for i in range(1, size):
        u = points[i]
        cost_back = dists[u][S]
        if dp[full_mask][i] + cost_back < ans:
            ans = dp[full_mask][i] + cost_back
            
    print(ans)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。