概要

この問題は、グラフ上の特定の地点（営業所 \(S\) および \(K\) 個の配達先 \(D_j\)）をすべて巡回して元の場所に戻る最短経路を求める問題です。いわゆる「巡回セールスマン問題 (TSP)」のバリエーションですが、地点間の移動が最短経路を通る必要があるため、事前の最短距離計算と動的計画法（Bit DP）を組み合わせて解きます。

考察

1. 巡回セールスマン問題への帰着

この問題の難しい点は、「どの順番で配達先を回るのが最適か」という点です。配達先の数 \(K\) は最大で 15 と非常に小さいことに注目しましょう。もし、営業所と各配達先の間の「最短移動時間」がすべて分かっていれば、この問題は典型的な 巡回セールスマン問題 として解くことができます。

2. 地点間の最短距離を求める

まず、以下の地点を「重要な地点」としてまとめます。 - 営業所 \(S\) - 配達先 \(D_1, D_2, \dots, D_K\)

これらの地点は合計で \(K+1\) 個（最大 16 個）あります。グラフ上の任意の 2 地点間の最短距離を求める必要がありますが、制約 \(N=10,000, M=20,000\) では、全地点間の最短距離を求めるワーシャル・フロイド法 (\(O(N^3)\)) は使えません。 代わりに、各「重要な地点」を始点として ダイクストラ法 を合計 \(K+1\) 回実行することで、必要な地点間の距離を効率的に求めることができます。

3. 状態の管理（Bit DP）

\(K\) 個の配達先を訪れたかどうかを集合で管理します。 - \(S = \{ \text{訪れた配達先の集合} \}\) - \(v = \text{現在いる配達先}\) この 2 つを状態として持つ動的計画法（Bit DP）を利用します。

アルゴリズム

1. グラフの構築: 与えられた道路情報を隣接リスト形式で保持します。
2. 最短距離行列の作成: 営業所 \(S\) および各配達先 \(D_j\) の計 \(K+1\) 箇所からダイクストラ法を実行し、これら相互の最短距離を格納した \((K+1) \times (K+1)\) の行列 dist_matrix を作成します。
3. Bit DP による最適化: 以下の DP テーブルを定義します。 dp[mask][i] := 配達先の訪問状態が mask（ビット集合）であり、最後に配達先 \(D_i\) に到達したときの最小移動時間。
   • 初期化: 営業所 \(S\) から各配達先 \(D_i\) への移動時間を dp[1 << i][i] にセットします。
   • 遷移: 現在の状態 (mask, i) から、まだ訪れていない配達先 \(D_j\) へ移動する場合、 dp[mask | (1 << j)][j] = min(dp[mask | (1 << j)][j], dp[mask][i] + dist_matrix[i+1][j+1]) と更新します。
4. 最終回答の計算: すべての配達先を訪れた状態 dp[(1 << K) - 1][i] に、最後に配達先 \(D_i\) から営業所 \(S\) へ戻る時間を加算し、その最小値を出力します。

計算量

• ダイクストラ法: \(O(K \cdot M \log N)\)
  • 1 回あたり \(O(M \log N)\) のダイクストラ法を \(K+1\) 回行います。
• Bit DP: \(O(K^2 \cdot 2^K)\)
  • 状態数が \(K \cdot 2^K\) で、各状態からの遷移が \(K\) 通りです。

\(K=15\) のとき、\(K^2 \cdot 2^K \approx 225 \times 32,768 \approx 7.3 \times 10^6\) となり、制限時間内に十分収まります。

• 合計時間計算量: \(O(K \cdot M \log N + K^2 \cdot 2^K)\)
• 空間計算量: \(O(N + M + K \cdot 2^K)\)

実装のポイント

• ダイクストラ法の高速化: 各ダイクストラ法の実行において、すべての「重要な地点」の最短距離が確定した時点で探索を打ち切る（早期終了）ことで、実行時間を短縮できます。

• Bit DP のインデックス: dist_matrix の 0 番目を営業所 \(S\)、1 番目以降を配達先 \(D_1 \dots D_K\) と対応させると、DP の遷移が書きやすくなります。

• Python での高速化: sys.stdin.read().split() による一括入力や、heapq の直接参照などを利用すると、Python でも高速に動作します。

  ソースコード

import sys
import heapq

def solve():
    # Read all input at once for faster processing
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    ptr = 0
    N = int(input_data[ptr])
    ptr += 1
    M = int(input_data[ptr])
    ptr += 1
    
    # Adjacency list representation of the graph
    adj = [[] for _ in range(N + 1)]
    for _ in range(M):
        u = int(input_data[ptr])
        ptr += 1
        v = int(input_data[ptr])
        ptr += 1
        w = int(input_data[ptr])
        ptr += 1
        adj[u].append((v, w))
        adj[v].append((u, w))
        
    # Starting location and delivery locations
    S = int(input_data[ptr])
    ptr += 1
    K = int(input_data[ptr])
    ptr += 1
    D = [int(input_data[ptr + i]) for i in range(K)]
    
    # All points of interest (starting point + delivery points)
    nodes = [S] + D
    num_nodes = K + 1
    
    # Shortest path distances between all pairs of nodes in 'nodes'
    dist_matrix = [[0] * num_nodes for _ in range(num_nodes)]
    
    # Map intersection ID to its index in the 'nodes' list for early exit in Dijkstra
    is_node = [-1] * (N + 1)
    for idx, node in enumerate(nodes):
        is_node[node] = idx
        
    heappop = heapq.heappop
    heappush = heapq.heappush
    INF = 10**18
    
    # Run Dijkstra's algorithm from each point of interest
    for i in range(num_nodes):
        start_node = nodes[i]
        distances = [INF] * (N + 1)
        distances[start_node] = 0
        pq = [(0, start_node)]
        
        found_count = 0
        while pq:
            d, u = heappop(pq)
            if d > distances[u]:
                continue
            
            # Count how many target points of interest we've found
            if is_node[u] != -1:
                found_count += 1
                # If all targets are reached from this source, we can stop the search
                if found_count == num_nodes:
                    break
                    
            for v, w in adj[u]:
                new_dist = d + w
                if distances[v] > new_dist:
                    distances[v] = new_dist
                    heappush(pq, (new_dist, v))
        
        # Store distances to other points of interest in the matrix
        for j in range(num_nodes):
            dist_matrix[i][j] = distances[nodes[j]]
            
    # Traveling Salesperson Problem (TSP) using Dynamic Programming
    # dp[mask][i] is the minimum distance to visit delivery nodes in 'mask', ending at delivery node D[i]
    dp = [[INF] * K for _ in range(1 << K)]
    
    # Initial state: travel from starting point S to each delivery node
    for i in range(K):
        # dist_matrix[0][i+1] is distance from nodes[0] (S) to nodes[i+1] (D[i])
        dp[1 << i][i] = dist_matrix[0][i+1]
        
    # Transition: visit more delivery nodes
    for mask in range(1, 1 << K):
        dp_mask = dp[mask]
        for i, d_i in enumerate(dp_mask):
            if d_i >= INF:
                continue
            
            # Current distance to reach D[i] after visiting nodes in 'mask'
            dist_matrix_i_plus_1 = dist_matrix[i+1]
            for j in range(K):
                # If delivery node D[j] has not been visited yet
                if not (mask & (1 << j)):
                    next_mask = mask | (1 << j)
                    new_dist = d_i + dist_matrix_i_plus_1[j+1]
                    if dp[next_mask][j] > new_dist:
                        dp[next_mask][j] = new_dist
                        
    # Final step: return to starting point S after visiting all delivery nodes
    ans = INF
    full_mask = (1 << K) - 1
    final_dp = dp[full_mask]
    for i in range(K):
        # dist_matrix[i+1][0] is the distance from D[i] to S
        res = final_dp[i] + dist_matrix[i+1][0]
        if res < ans:
            ans = res
            
    # Output the minimum total travel time
    print(ans)

if __name__ == '__main__':
    solve()

---

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