概要

指定された始点 \(S\) から出発し、\(K\) 個の特定の届け先をすべて訪れた後、再び始点 \(S\) に戻るための最小コストを求める問題です。

考察

• 高橋君が移動する経路上で重要なのは、始点 \(S\) と \(K\) 個の届け先 \(T_1, \dots, T_K\) の間をどのように移動するかです。
• まず、これら \(K+1\) 個の地点間の最短距離が分かっていれば、問題は「\(K+1\) 個の都市を巡る巡回セールスマン問題 (TSP)」に帰着できます。
• 届け先を訪れる順序をすべて試す（順列を全探索する）と、最大で \(15! \approx 1.3 \times 10^{12}\) 通りとなり、実行時間制限に間に合わずTLE（時間切れ）になってしまいます。
• しかし、届け先の数 \(K\) が最大 \(15\) と非常に小さいことに着目すると、bit DP（動的計画法）を用いることで、順列の全探索を大幅に高速化し現実的な時間で解くことができます。

アルゴリズム

この問題は大きく分けて「最短距離の事前計算」と「bit DP による巡回経路の探索」の2つのステップで解くことができます。

1. 最短距離の事前計算 (ダイクストラ法) 始点 \(S\) と \(K\) 個の届け先 \(T_1, \dots, T_K\) を合わせた \(K+1\) 個の地点を「重要な地点」とします。 これらの重要な地点をそれぞれ始点として、ダイクストラ法を合計 \(K+1\) 回実行します。これにより、重要な地点間のすべてのペアについて、最短距離をまとめた行列（距離行列）を作成します。

2. 巡回経路の探索 (bit DP) 重要な地点に \(0\) から \(K\) までの番号を付けます。始点 \(S\) を \(0\) 番、届け先 \(T_1, \dots, T_K\) をそれぞれ \(1\) 番から \(K\) 番とします。 次のような DP テーブルを定義します：

   • \(dp[\text{mask}][i]\)：これまでに訪れた届け先の集合が \(\text{mask}\)（2進数のビットで表現）で、現在いる地点が \(i\) であるような経路の最小コスト。

初期化: \(dp[0][0] = 0\)（まだどの届け先も訪れておらず、地点 \(S\) にいる状態）、それ以外は無限大 (\(\infty\)) とします。

遷移: 現在の状態 \(dp[\text{mask}][i]\) から、まだ訪れていない届け先 \(j\) （\(\text{mask}\) の \(j-1\) 番目のビットが \(0\)）へ移動することを考えます。 $\(dp[\text{mask} \cup \{j\}][j] = \min(dp[\text{mask} \cup \{j\}][j], dp[\text{mask}][i] + \text{dist}[i][j])\)\( ここで、\)\text{dist}[i][j]\( はステップ1で求めた地点 \)i\( から地点 \)j$ への最短距離です。

1. 答えの計算 すべての届け先を訪れた状態（\(\text{mask}\) の \(K\) 個のビットがすべて \(1\)）から、最後に始点 \(S\) （\(0\) 番）に戻る必要があります。 各地点 \(i\) について、\(dp[\text{全届け先訪問}][i] + \text{dist}[i][0]\) の最小値を求めます。これが求める答えです。もし最小値が無限大のままであれば、すべての届け先を訪れて戻ることが不可能として -1 を出力します。

計算量

• 時間計算量: \(O(K M \log N + 2^K K^2)\)
  • ダイクストラ法を \(K+1\) 回実行するため、\(O(K M \log N)\) かかります。
  • bit DP の状態数は \(2^K \times (K+1)\) で、それぞれについて \(K\) 通りの遷移を試すため、\(O(2^K K^2)\) かかります。
  • \(K \le 15, N \le 300, M \le 90000\) の制約のもとでは、十分に高速に動作します。
• 空間計算量: \(O(N + M + 2^K K)\)
  • グラフの保持に \(O(N + M)\)、距離行列に \(O(K^2)\)、DPテーブルに \(O(2^K K)\) のメモリを使用します。

実装のポイント

• ビット演算の活用: 訪れた届け先の集合 \(\text{mask}\) は整数で管理します。「\(j\) 番目の届け先を訪れたか」は mask & (1 << (j - 1)) で判定し、新たに訪れる場合は mask | (1 << (j - 1)) で状態を更新します。

• インデックスの管理: 始点 \(S\) をインデックス \(0\) とし、届け先を \(1\) から \(K\) に対応させると、DP の状態管理や距離行列の参照が分かりやすくなります。

• 非連結グラフへの対応: 道路が存在せず到達できない場合は、距離を無限大 (float('inf')) として扱います。DP の遷移時や、最終的な答えの計算時に無限大のままなら計算から除外する処理を忘れないようにしましょう。

  ソースコード

import sys
import heapq

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    
    adj = [[] for _ in range(N + 1)]
    idx = 2
    for _ in range(M):
        u = int(input_data[idx])
        v = int(input_data[idx+1])
        w = int(input_data[idx+2])
        adj[u].append((v, w))
        idx += 3
        
    S = int(input_data[idx])
    K = int(input_data[idx+1])
    idx += 2
    
    T = []
    for _ in range(K):
        T.append(int(input_data[idx]))
        idx += 1
        
    targets = [S] + T
    K_total = K + 1
    
    dist_matrix = [[float('inf')] * K_total for _ in range(K_total)]
    
    for i in range(K_total):
        start_node = targets[i]
        dist = [float('inf')] * (N + 1)
        dist[start_node] = 0
        pq = [(0, start_node)]
        
        while pq:
            d, u = heapq.heappop(pq)
            if d > dist[u]:
                continue
            for v, w in adj[u]:
                if dist[v] > d + w:
                    dist[v] = d + w
                    heapq.heappush(pq, (dist[v], v))
                    
        for j in range(K_total):
            dist_matrix[i][j] = dist[targets[j]]
            
    INF = float('inf')
    dp = [[INF] * K_total for _ in range(1 << K)]
    dp[0][0] = 0
    
    for mask in range(1 << K):
        dp_mask = dp[mask]
        for i in range(K_total):
            curr_cost = dp_mask[i]
            if curr_cost == INF:
                continue
            dist_i = dist_matrix[i]
            for j in range(1, K_total):
                if not (mask & (1 << (j - 1))):
                    nxt_mask = mask | (1 << (j - 1))
                    cost = curr_cost + dist_i[j]
                    if dp[nxt_mask][j] > cost:
                        dp[nxt_mask][j] = cost
                        
    ans = INF
    full_mask = (1 << K) - 1
    for i in range(K_total):
        if dp[full_mask][i] != INF and dist_matrix[i][0] != INF:
            if ans > dp[full_mask][i] + dist_matrix[i][0]:
                ans = dp[full_mask][i] + dist_matrix[i][0]
                
    if ans == INF:
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    solve()

この解説は gemini-3.1-pro-thinking によって生成されました。