AcWing 91. 最短 Hamilton 路径

◎

本节目标

用位掩码记录已访问节点，固定起点和终点求最短路径。

题意与约束

从 0 出发，恰好访问每个节点一次并固定到 n-1 结束，求最短路径。

第一反应与重复子问题

路径顺序有阶乘种，但到达同一“已访问集合和末点”后的后续选择完全相同。

状态定义与转移推导

概念上，dp[mask][last] 是从 0 到 last 并访问集合 mask 的最短距离。实现中 0 始终已访问，因此掩码只记录 1..n-1；向任何未访问 next 扩展，答案取全掩码且末点为 n-1 的状态。

正确性依据

任一合法路径去掉最后一条边后，前缀正好是一个更小集合的最优子问题；对所有末边枚举即可覆盖所有路径。

样例执行过程

四点矩阵从 {0} 开始扩展，完成集合且末点为 3 的最短距离为 15。

代码实现

C++

C++17

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int shortestHamiltonPath(const vector<vector<int>>& graph) {
    int n = static_cast<int>(graph.size());
    if (n <= 1) {
        return 0;
    }
    const int INF = 0x3f3f3f3f;
    int states = 1 << n;
    vector<int> dp(states * n, INF);
    dp[n] = 0;
    for (int mask = 1; mask < states; mask++) {
        for (int last = 0; last < n; last++) {
            if (!(mask & (1 << last))) {
                continue;
            }
            int current = dp[mask * n + last];
            if (current == INF) {
                continue;
            }
            for (int nxt = 0; nxt < n; nxt++) {
                if (!(mask & (1 << nxt))) {
                    int nextMask = mask | (1 << nxt);
                    dp[nextMask * n + nxt] = min(
                        dp[nextMask * n + nxt],
                        current + graph[last][nxt]
                    );
                }
            }
        }
    }
    return dp[(states - 1) * n + n - 1];
}

#ifndef ALGORITHM_TUTORIAL_NO_MAIN
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) {
        return 0;
    }
    vector<vector<int>> graph(n, vector<int>(n));
    for (auto& row : graph) {
        for (int& value : row) {
            cin >> value;
        }
    }
    cout << shortestHamiltonPath(graph);
}
#endif

Python

Python 3

from array import array
import sys


def shortest_hamilton_path(graph):
    n = len(graph)
    if n <= 1:
        return 0
    width = n - 1
    states = 1 << (n - 1)
    full = states - 1
    INF = 0xFFFFFFFF
    dp = array('I', [INF]) * (states * width)

    for nxt in range(width):
        dp[(1 << nxt) * width + nxt] = graph[0][nxt + 1]

    for mask in range(1, states):
        base = mask * width
        remaining = full ^ mask
        endpoints = mask
        while endpoints:
            last_bit = endpoints & -endpoints
            last = last_bit.bit_length() - 1
            current = dp[base + last]
            if current != INF:
                next_bits = remaining
                row = graph[last + 1]
                while next_bits:
                    next_bit = next_bits & -next_bits
                    nxt = next_bit.bit_length() - 1
                    next_index = (mask | next_bit) * width + nxt
                    candidate = current + row[nxt + 1]
                    if candidate < dp[next_index]:
                        dp[next_index] = candidate
                    next_bits ^= next_bit
            endpoints ^= last_bit
    return dp[full * width + width - 1]


def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if data:
        n = data[0]
        graph = [data[1 + row * n:1 + (row + 1) * n] for row in range(n)]
        print(shortest_hamilton_path(graph))


if __name__ == '__main__':
    main()

复杂度分析

时间 O(2^n n²)，空间 O(2^n n)。两份实现都用连续整数表；Python 省去恒为已访问的起点位，并以紧凑的 32 位数组保存其余 n-1 个节点的状态，n=20 时 DP 表约为 40 MiB。

边界与易错点

单点图答案为零；终点必须固定为 n-1，大权值图的无穷大也要大于可能答案。

模式迁移

访问有限集合且末位置重要时使用集合 DP；不要求访问全部节点时通常转为最短路问题。回到状态压缩动态规划。