最短Hamilton路径
给定一张 n (n<=20) 个点的带权无向图，点从 0 ~ n - 1 编号，求起点 0 到终点 n - 1 的最短Hamilton路径。
Hamilton路径的定义为从 0 到 n - 1 不重不漏地经过每个点恰好一次。
// 最短Hamilton路径
// n个点带权无向图，从0到n-1的最短(每个点经过恰好一次)路径
#include<bits/stdc++.h>
#define reg register
using namespace std;
// 从输入流中读取一个整数
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
// 将一个整数写入输出流
inline void write(int x){
if(x<0){
putchar('-');
x=-x;
}
if(x>9) write(x/10);
putchar(x%10+'0');
return ;
}
const int MAXN=22; // 定义最大节点数为22
int n,f[1<<20][20],mapp[MAXN][MAXN]; // n为节点数，f为动态规划数组，mapp为邻接矩阵表示的权重
// 实现Hamiltonian路径搜索算法，返回从0到n-1的最短路径长度
int hamilton(){
memset(f,0x3f,sizeof(f)); // 将f数组初始化为无穷大，除了起点的权重为0
f[1][0]=0; // 起点到自身的权重为0
for(reg int i=1;i<1<<n;i++){ // 对于所有可能的状态进行遍历
for(reg int j=0;j<n;j++){ // 对于每个节点进行遍历
if(i>>j&1){ // 如果该节点被选中(即i的第j位为1)
for(reg int k=0;k<n;k++){ // 对于其他节点进行遍历
if((i^1<<j)>>k&1){ // 如果该节点未被选中且可以到达(即i的第j位为0且从该节点到达其他节点存在一条路径)
f[i][j]=min(f[i][j],f[i^1<<j][k]+mapp[k][j]); // 更新当前状态的最小路径长度为原最小路径长度加上从其他节点到达该节点的权重之和
}
}
}
}
}
return f[(1<<n)-1][n-1]; // 返回从起点到终点的最短路径长度
}
int main(){ // 主函数入口
n=read(); // 从输入流中读取节点数并存入n
for(reg int i=1;i<=n;i++){ // 对于每个节点，读取其与其他节点之间的权重并存入邻接矩阵mapp中
for(reg int j=1;j<=n;j++){
mapp[i][j]=read();
}
}
write(hamilton()); // 将从起点到终点的最短路径长度写入输出流中并返回结果
return 0; // 程序正常结束，返回0表示成功执行完毕
}