Official

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

gpt-5.3-codex

概要

「地点 \(1\) から出発して、指定された \(K\) 個の届け先をすべて回って \(1\) に戻る最短時間」を求める問題です。
本質は、重要な地点間の最短距離を先に求めてから、\(K \le 15\) を活かした bit DP(巡回セールスマン型DP)で解くことです。

考察

この問題で厄介なのは、グラフ全体の頂点数 \(N,M\) が最大 \(5\times 10^4\) と大きい一方、必ず訪れるべき届け先は \(K\le 15\) と小さいことです。

まず素朴に「グラフ上で状態を持って探索(今どこにいて、どの届け先を訪問済みか)」をすると、状態数が \(N \times 2^K\) になり大きすぎます。
最大で \(5\times 10^4 \times 2^{15}\) となり、現実的ではありません。

ここで重要な観察は次の通りです。

  • 実際に最適化したいのは「地点 \(1\) と届け先 \(K\) 個」だけ(合計 \(K+1\) 個)
  • それらの間の移動コストは、元グラフ上の最短距離に置き換えてよい
    (最短経路同士をつないでも、三角不等式により損しない)

つまり、元グラフを直接DPするのではなく、

  1. 重要地点(\(1\) と \(V_i\) たち)間の最短距離行列を作る
  2. その完全グラフ上で「全届け先を回って戻る最小コスト」を bit DP で解く

という二段構えにすれば高速に解けます。

アルゴリズム

  1. 重要地点配列を important = [1] + V とする(長さ \(L=K+1\))。
  2. 各重要地点を始点にダイクストラを実行し、他の重要地点までの最短距離を pair[i][j] に記録する。
    • これで「重要地点間の距離表」が完成。
  3. bit DP を行う。
    • dp[mask][i]
      = 「地点 \(1\) から出発し、mask で表される届け先集合を訪問済みで、最後に届け先 i(0-based)にいるときの最小コスト」
  4. 初期化:
    • dp[1<<i][i] = pair[0][i+1]
      (\(1\) から各届け先へ直接行く)
  5. 遷移:
    • dp[mask][i] から未訪問 j に移る
      dp[mask | (1<<j)][j] = min(..., dp[mask][i] + pair[i+1][j+1])
  6. 全訪問 full=(1<<K)-1 の後、各終点 i から地点 \(1\) に戻るコストを足して最小値を取る。
    • ans = min(dp[full][i] + pair[i+1][0])

これがコード中の処理と一致しています。

計算量

  • 時間計算量:
    ダイクストラを \(K+1\) 回行うので
    \(O((K+1)\, M \log N)\)
    • bit DP が \(O(2^K K^2)\)
      よって全体は
      \(O((K+1)M\log N + 2^K K^2)\)
  • 空間計算量:
    グラフ \(O(N+M)\)、距離表 \(O((K+1)^2)\)、DP表 \(O(2^K K)\)
    合計で \(O(N+M+2^K K)\)

実装のポイント

  • 辺重みが正なので最短路はダイクストラでOK。

  • 距離や答えは最大で大きくなるため、INF = 10**30 のように十分大きい値を使う。

  • dijkstra 内の if d != dist[v]: continue は、古いヒープ要素を捨てる定番高速化。

  • インデックス対応に注意:

    • pair[0] が地点 \(1\)
    • pair[i+1] が届け先 V[i]
  • 最後に「戻るコスト(終点→1)」を必ず足すのを忘れない。

    ソースコード

import sys
import heapq

def dijkstra(start, graph, n):
    INF = 10**30
    dist = [INF] * (n + 1)
    dist[start] = 0
    pq = [(0, start)]
    while pq:
        d, v = heapq.heappop(pq)
        if d != dist[v]:
            continue
        for nv, w in graph[v]:
            nd = d + w
            if nd < dist[nv]:
                dist[nv] = nd
                heapq.heappush(pq, (nd, nv))
    return dist

def main():
    input = sys.stdin.readline
    N, M, K = map(int, input().split())
    V = list(map(int, input().split()))
    
    graph = [[] for _ in range(N + 1)]
    for _ in range(M):
        a, b, c = map(int, input().split())
        graph[a].append((b, c))
        graph[b].append((a, c))
    
    important = [1] + V  # index 0 is node 1, indices 1..K are destinations
    L = K + 1
    
    # Pairwise shortest paths among important nodes
    pair = [[0] * L for _ in range(L)]
    for i in range(L):
        dist = dijkstra(important[i], graph, N)
        for j in range(L):
            pair[i][j] = dist[important[j]]
    
    INF = 10**30
    # dp[mask][i]: minimum cost to start from node 1, visit destinations in mask,
    # and end at destination i (0-based for V list)
    size = 1 << K
    dp = [[INF] * K for _ in range(size)]
    
    for i in range(K):
        dp[1 << i][i] = pair[0][i + 1]
    
    for mask in range(size):
        row = dp[mask]
        for i in range(K):
            cur = row[i]
            if cur >= INF:
                continue
            for j in range(K):
                if (mask >> j) & 1:
                    continue
                nmask = mask | (1 << j)
                nd = cur + pair[i + 1][j + 1]
                if nd < dp[nmask][j]:
                    dp[nmask][j] = nd
    
    full = (1 << K) - 1
    ans = INF
    for i in range(K):
        val = dp[full][i] + pair[i + 1][0]
        if val < ans:
            ans = val
    
    print(ans)

if __name__ == "__main__":
    main()

この解説は gpt-5.3-codex によって生成されました。

posted:
last update: