Official

E - 配達員の巡回 / Delivery Person's Round Editorial by admin

Gemini 3.0 Flash (Thinking)

概要

この問題は、地点 1 を出発して \(K\) 個の指定された地点をすべて巡回し、再び地点 1 に戻る際の最短経路を求める問題です。 地点数 \(N\) や道の数 \(M\) は大きいですが、巡回すべき地点の数 \(K\) が最大 15 と非常に小さいことが特徴です。

考察

1. 必要な情報の整理

地点は \(N\) 個ありますが、私たちが特に関心があるのは「地点 1」と「届け先の \(K\) 個の地点」の合計 \(K+1\) 個の地点だけです。 地点 \(A\) から地点 \(B\) へ移動する際、その途中にある他の地点が届け先でなければ、単に最短経路で通過すればよいことになります。

したがって、この問題は以下の 2 ステップに分解できます。 1. 地点 1 および \(V_1, \dots, V_K\) の間の全ペア間の最短距離を求める。 2. 求めた距離を用いて、いわゆる巡回セールスマン問題 (TSP) を解く。

2. なぜ素朴な方法ではダメなのか

巡回する順番を全探索しようとすると、その組み合わせは \(K!\) 通りになります。\(K=15\) のとき \(15! \approx 1.3 \times 10^{12}\) となり、制限時間内に計算が終わりません。 そこで、動的計画法(DP)を用いることで、この計算量を \(O(2^K \cdot K^2)\) 程度に抑えることができます。\(2^{15} \cdot 15^2 \approx 7.3 \times 10^6\) であり、これなら十分に間に合います。

アルゴリズム

ステップ 1: 全ペア間の最短距離の計算

地点 1 と各届け先 \(V_i\)(合計 \(K+1\) 箇所)を始点として、それぞれダイクストラ法を実行します。 - 1 回のダイクストラ法で、ある始点から他のすべての地点への最短距離が求まります。 - これを \(K+1\) 回繰り返すことで、必要な地点間の距離をすべて網羅した \((K+1) \times (K+1)\) の距離行列 dist_matrix を作成します。

ステップ 2: ビット DP による巡回セールスマン問題

「どの地点を訪れたか」という集合をビットマスク(整数値)で表し、以下の DP を行います。

  • DPの状態定義: dp[mask][i] := すでに訪れた届け先の集合が mask であり、現在地が届け先 \(V_i\) であるときの最小コスト (※ mask は \(K\) ビットの整数で、\(j\) 番目のビットが 1 なら \(V_j\) を訪問済みであることを示します)

  • 初期状態: 地点 1 から各届け先 \(V_i\) へ直接向かうコストを入れます。 dp[1 << i][i] = dist_matrix[0][i+1] (0 は地点 1、i+1 は \(V_i\) に対応)

  • 遷移: 現在の状態 dp[mask][i] から、まだ訪れていない届け先 \(V_j\) へ移動する場合: dp[mask | (1 << j)][j] = min(dp[mask | (1 << j)][j], dp[mask][i] + dist_matrix[i+1][j+1])

  • 最終回答: すべての届け先を訪れた状態 dp[(1 << K) - 1][i] に、現在地 \(V_i\) から地点 1 に戻るコスト dist_matrix[i+1][0] を加えたものの最小値が答えとなります。

計算量

  • 時間計算量: \(O(K(N + M) \log N + 2^K \cdot K^2)\)
    • ダイクストラ法 \(K+1\) 回分:\(O(K(N + M) \log N)\)
    • ビット DP 部分:\(O(2^K \cdot K^2)\)
  • 空間計算量: \(O(N + M + 2^K \cdot K)\)
    • グラフの隣接リスト、ダイクストラ法の距離配列、DP テーブルの保持に必要なメモリです。

実装のポイント

  • ダイクストラ法の効率化: ダイクストラ法を実行する際、その回の始点から「関心のある \(K+1\) 個の地点」すべてへの距離が確定した時点で探索を打ち切る(break する)ことで、実行時間を短縮できます。

  • 高速な入出力: \(N, M\) が大きいため、Python では sys.stdin.read().split() などを用いて一括で入力を読み込むのが効果的です。

  • ビット演算: mask & (1 << j) で訪問済み判定、mask | (1 << j) で訪問フラグを立てる操作など、ビット演算を正確に行う必要があります。

    ソースコード

import heapq
import sys

def solve():
    # Use fast I/O to read all input at once
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: number of locations, M: number of roads, K: number of destinations
    N = int(input_data[0])
    M = int(input_data[1])
    K = int(input_data[2])
    
    # V: list of destination locations
    V = [int(x) for x in input_data[3:3+K]]
    
    # Build adjacency list for the graph
    adj = [[] for _ in range(N + 1)]
    idx = 3 + K
    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))
        adj[v].append((u, w))
        idx += 3
        
    # The locations we are interested in: starting point (1) and all destinations (V)
    nodes = [1] + V
    num_nodes = K + 1
    
    # Precompute shortest paths between all pairs of interest using Dijkstra
    # We run Dijkstra from each of the K+1 nodes.
    dist_matrix = [[0] * num_nodes for _ in range(num_nodes)]
    is_target = [False] * (N + 1)
    for node in nodes:
        is_target[node] = True
        
    for i in range(num_nodes):
        start_node = nodes[i]
        dists = [float('inf')] * (N + 1)
        dists[start_node] = 0
        pq = [(0, start_node)]
        
        count = 0
        visited_targets = [False] * (N + 1)
        
        while pq:
            d, u = heapq.heappop(pq)
            if d > dists[u]:
                continue
            
            # If we popped a node of interest, record it.
            # Once we've popped all interest nodes, we can stop Dijkstra for this start_node.
            if is_target[u] and not visited_targets[u]:
                visited_targets[u] = True
                count += 1
                if count == num_nodes:
                    break
            
            for v, w in adj[u]:
                new_d = d + w
                if dists[v] > new_d:
                    dists[v] = new_d
                    heapq.heappush(pq, (new_d, v))
        
        # Fill the distance matrix for the interest nodes
        for j in range(num_nodes):
            dist_matrix[i][j] = dists[nodes[j]]
            
    # TSP using Bitmask DP
    # dp[mask][i] is the minimum distance to visit the set of destinations in 'mask',
    # ending at destination V[i].
    # 'mask' is a bitmask of length K where the j-th bit represents destination V[j].
    INF = float('inf')
    dp = [[INF] * K for _ in range(1 << K)]
    
    # Initial step: move from location 1 (nodes[0]) to each destination V[i] (nodes[i+1])
    for i in range(K):
        dp[1 << i][i] = dist_matrix[0][i+1]
        
    # Iterate through all masks (sets of visited destinations)
    for mask in range(1, 1 << K):
        dp_mask = dp[mask]
        for i in range(K):
            d_curr = dp_mask[i]
            if d_curr == INF:
                continue
            
            # Try moving from the current destination V[i] to a next destination V[j]
            dist_row = dist_matrix[i+1]
            for j in range(K):
                if not (mask & (1 << j)):
                    new_mask = mask | (1 << j)
                    new_dist = d_curr + dist_row[j+1]
                    if dp[new_mask][j] > new_dist:
                        dp[new_mask][j] = new_dist
                        
    # Final step: from the last visited destination back to location 1
    ans = INF
    full_mask = (1 << K) - 1
    dist_from_start = dist_matrix[0] # dist_matrix is symmetric, dist_matrix[0][i+1] == dist_matrix[i+1][0]
    dp_full = dp[full_mask]
    for i in range(K):
        # Total cycle: 1 -> ... -> V[i] -> 1
        res = dp_full[i] + dist_from_start[i+1]
        if res < ans:
            ans = res
            
    print(ans)

if __name__ == '__main__':
    solve()

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