P10447 最短 Hamilton 路径题目描述给定一张nnn个点的带权无向图点从0∼n−10 \sim n-10∼n−1标号求起点000到终点n−1n-1n−1的最短 Hamilton 路径。Hamilton 路径的定义是从000到n−1n-1n−1不重不漏地经过每个点恰好一次。输入格式第一行输入整数nnn。接下来nnn行每行nnn个整数其中第iii行第jjj个整数表示点i−1i-1i−1到j−1j-1j−1的距离记为a[i−1,j−1]a[i-1,j-1]a[i−1,j−1]。对于任意的x,y,zx,y,zx,y,z数据保证a[x,x]0a[x,y]a[y,x]a[x,x]0a[x,y]a[y,x]a[x,x]0a[x,y]a[y,x]并且a[x,y]a[y,z]≥a[x,z]a[x,y]a[y,z] \ge a[x,z]a[x,y]a[y,z]≥a[x,z]。输出格式输出一个整数表示最短 Hamilton 路径的长度。输入输出样例 #1输入 #15 0 2 4 5 1 2 0 6 5 3 4 6 0 8 3 5 5 8 0 5 1 3 3 5 0输出 #118说明/提示对于所有测试数据满足1≤n≤201 \le n \le 201≤n≤200≤a[i,j]≤1070 \le a[i,j] \le 10^70≤a[i,j]≤107C实现#includebits/stdc.husingnamespacestd;constintMAXN25,MAXM(120),inf0x3f;//定义变量inf为无限intn,a[MAXN][MAXN],f[MAXM][MAXN];intmain(){scanf(%d,n);for(inti0;in;i)for(intj0;jn;j)scanf(%d,a[i][j]);memset(f,inf,sizeof(f));//一开始f数组都是无限的f[1][0]0;//还没开始旅程为0for(inti1;i(1n);i)//枚举状态{for(intj0;jn;j)//枚举每个点{if(!((ij)1))continue;//经过了for(intk0;kn;k)//上一次经过了哪些点if(((i^(1j))k)1)//枚举从上一个经过的节点走到j节点f[i][j]min(f[i][j],f[i^(1j)][k]a[k][j]);//状态转移}}printf(%d\n,f[(1n)-1][n-1]);//outreturn0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容