概要

一方通行の道路があるグラフ上で、営業所 \(S\) を出発し、\(K\) 個（最大15個）の届け先すべてを訪れて \(S\) に戻る最小コストを求める問題です。巡回セールスマン問題（TSP）のバリエーションであり、全頂点間最短距離の前計算とビットマスクDPを組み合わせて解きます。

考察

重要な気づき

1. 訪問順序が自由: \(K\) 個の届け先を好きな順番で回れるため、最適な訪問順序を見つける必要があります。\(K\) 個の順列は \(K!\) 通りで、\(K = 15\) だと約 \(1.3 \times 10^{12}\) 通りとなり全列挙は不可能です。

2. 中間地点の通過は気にしなくてよい: ある届け先から別の届け先へ移動する際、途中で別の届け先を通過したら、それも「訪問済み」として扱えます。しかし、最短経路を使って移動する限り、重要なのは「どの届け先を訪問済みか」と「今どの地点にいるか」だけです。

3. 関心のある地点は少数: グラフは最大300頂点ありますが、実際に「どこにいるか」を区別する必要があるのは \(S\) と \(K\) 個の届け先、合計 \(K+1\) 個（最大16個）だけです。それ以外の地点は中継地に過ぎないため、事前に全頂点間最短距離を求めておけば、これら少数の「キーとなる地点」間の移動コストだけで問題を解けます。

素朴なアプローチの問題点

• 全順列を試す：\(O(K!)\) で \(K=15\) では計算不可能
• ダイクストラを都度実行：可能だが、Floyd-Warshall で一括計算する方が楽

アルゴリズム

ステップ1：全頂点間最短距離（Floyd-Warshall）

\(N \leq 300\) なので、Floyd-Warshall 法で全頂点ペア間の最短距離 \(\mathrm{dist}[i][j]\) を \(O(N^3)\) で計算します。

ステップ2：キーとなる地点の距離行列

キーとなる地点を \(\{S, T_1, T_2, \ldots, T_K\}\) の \(K+1\) 個とします。これらの間の最短距離を \(d[i][j] = \mathrm{dist}[\text{nodes}[i]][\text{nodes}[j]]\) として抽出します（\(\text{nodes}[0] = S\), \(\text{nodes}[j] = T_j\)）。

ステップ3：ビットマスクDP（巡回セールスマン問題）

• 状態: \(\mathrm{dp}[\text{mask}][i]\) = 届け先の訪問状態が \(\text{mask}\)（\(K\) ビット）で、現在キー地点 \(i\) にいるときの最小コスト
• 初期状態: \(\mathrm{dp}[0][0] = 0\)（\(S\) にいて、どこにも届けていない）
• 遷移: 現在地 \(u\) からキー地点 \(v\) へ最短距離 \(d[u][v]\) で移動。\(v\) が届け先なら対応するビットを立てる
• 答え: \(\min_i \left(\mathrm{dp}[\text{full\_mask}][i] + d[i][0]\right)\)（全届け先訪問後に \(S\) へ戻る）

具体例として、\(K=2\) で届け先が \(T_1, T_2\) の場合： - \(\text{mask} = 00\)：どちらも未訪問 - \(\text{mask} = 01\)：\(T_1\) のみ訪問済み - \(\text{mask} = 11\)：両方訪問済み → \(S\) に戻ればゴール

状態数は \(2^K \times (K+1)\) で、各状態から \(K+1\) 通りの遷移があるため、DP部分は \(O(2^K \cdot K^2)\) です。

計算量

• 時間計算量: \(O(N^3 + 2^K \cdot K^2)\)
  • Floyd-Warshall: \(O(N^3) = O(300^3) = O(2.7 \times 10^7)\)
  • ビットマスクDP: \(O(2^{15} \times 16^2) \approx O(8.4 \times 10^6)\)
• 空間計算量: \(O(N^2 + 2^K \cdot K)\)
  • 距離行列: \(O(N^2)\)
  • DPテーブル: \(O(2^K \cdot K)\)

実装のポイント

• Floyd-Warshall の初期化: 自分自身への距離は \(0\)、辺がない箇所は \(\infty\) に初期化。多重辺はないが、念のため最小値を取る。

• INF の扱い: Python では float('inf') を使うと整数演算の誤差を気にせず済む。

• DP の遷移順序: \(\text{mask}\) を小さい方から順に処理すれば、ビットが立つ方向にしか遷移しないため正しく計算できる。ただし \(S\) に戻る遷移（ビットが増えない）もあるので、最終的な答えは DP 完了後に全状態から \(S\) への帰還コストを加えて求める。

• \(S\) への帰還: dp[full_mask][0] だけでなく、dp[full_mask][i] + d[i][0] の最小値も確認する必要がある（全届け先を回った後、最後に \(S\) に戻る移動が残っている場合）。

  ソースコード

import sys
import heapq

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    
    INF = float('inf')
    
    # Floyd-Warshall for all-pairs shortest paths
    dist = [[INF] * (N + 1) for _ in range(N + 1)]
    for i in range(N + 1):
        dist[i][i] = 0
    
    for _ in range(M):
        u = int(input_data[idx]); idx += 1
        v = int(input_data[idx]); idx += 1
        w = int(input_data[idx]); idx += 1
        if w < dist[u][v]:
            dist[u][v] = w
    
    S = int(input_data[idx]); idx += 1
    K = int(input_data[idx]); idx += 1
    
    T = []
    for _ in range(K):
        T.append(int(input_data[idx])); idx += 1
    
    # Floyd-Warshall
    for k in range(1, N + 1):
        for i in range(1, N + 1):
            if dist[i][k] == INF:
                continue
            for j in range(1, N + 1):
                if dist[k][j] == INF:
                    continue
                nd = dist[i][k] + dist[k][j]
                if nd < dist[i][j]:
                    dist[i][j] = nd
    
    # Key nodes: S and T[0..K-1]
    # Index 0 = S, Index 1..K = T[0..K-1]
    nodes = [S] + T
    num_nodes = K + 1
    
    # Build distance matrix between key nodes
    d = [[INF] * num_nodes for _ in range(num_nodes)]
    for i in range(num_nodes):
        for j in range(num_nodes):
            d[i][j] = dist[nodes[i]][nodes[j]]
    
    # TSP with bitmask DP
    # State: (current node index in key nodes, visited bitmask of delivery points)
    # Delivery points are bits 0..K-1 corresponding to T[0..K-1]
    # We start at node index 0 (which is S), need to visit all K delivery points, return to S.
    
    full_mask = (1 << K) - 1
    
    # dp[mask][i] = minimum cost to have visited the delivery points in mask, currently at key node i
    dp = [[INF] * num_nodes for _ in range(1 << K)]
    
    # Start at S (index 0), no deliveries yet
    dp[0][0] = 0
    
    for mask in range(1 << K):
        for u in range(num_nodes):
            if dp[mask][u] == INF:
                continue
            cost_u = dp[mask][u]
            # Try going to each key node
            for v in range(num_nodes):
                if d[u][v] == INF:
                    continue
                new_cost = cost_u + d[u][v]
                if v == 0:
                    # Going back to S, no new delivery
                    new_mask = mask
                else:
                    # v corresponds to delivery point v-1
                    new_mask = mask | (1 << (v - 1))
                if new_cost < dp[new_mask][v]:
                    dp[new_mask][v] = new_cost
    
    # Answer: visit all deliveries and return to S
    ans = dp[full_mask][0]
    
    # But we also need to consider: after visiting all, we go back to S
    # dp[full_mask][0] is already the case where we're at S with all visited
    # But we might reach full_mask at some node i != 0, then go back to S
    for i in range(num_nodes):
        if dp[full_mask][i] != INF and d[i][0] != INF:
            val = dp[full_mask][i] + d[i][0]
            if val < ans:
                ans = val
    
    if ans == INF:
        print(-1)
    else:
        print(ans)

main()

---

この解説は claude4.6opus-thinking によって生成されました。