本文共 542 字，大约阅读时间需要 1 分钟。

哈密顿路径是连接图中所有顶点且仅访问一次的路径。对于n=4的图，从0-3的路径有两种可能（0-1-2-3和0-2-1-3），选择其中最短的一条即可。然而，当n达到20时，状态数为18！，暴力求解显然不可行。

目标是找到从0到19的最短路径。每个中间状态可以用n位二进制数表示，其中每一位代表一个顶点是否被访问。状态转移方程为：f[state][j] = min(f[state_k][k] + v[k][j])，其中state_k是state去掉k的状态。f[state][j]表示已访问某些顶点且当前在j的路径长度。

在代码实现中，首先初始化f数组为0x3f（二进制0011 1111，即9），表示无穷大。然后设定f[1][0]=0，表示只访问0顶点。对于每个state，从1到2^n-1，遍历每个顶点j，检查j是否在state中。如果在，更新f[state][j]的最小值。

状态转移方程对应代码：遍历顶点k，计算state_k = state - (1<<j)，并检查k是否在state_k中。如果在，则更新f[state][j] = min(f[state][j], f[state_k][k] + v[k][j])。需要注意，遍历顺序依次从i=1递增，确保后续状态优先处理。