制作微信网页的网站,wordpress 4.8上传漏洞,网站建设合约,网站大气是什么意思题目
给定一张 n 个点的带权无向图#xff0c;点从 0∼n−1 标号#xff0c;求起点 0 到终点 n−1 的最短 Hamilton 路径。
Hamilton 路径的定义是从 0 到 n−1 不重不漏地经过每个点恰好一次。
输入格式
第一行输入整数 n。
接下来 n 行每行 n 个整数#xff0c;其中第…题目
给定一张 n 个点的带权无向图点从 0∼n−1 标号求起点 0 到终点 n−1 的最短 Hamilton 路径。
Hamilton 路径的定义是从 0 到 n−1 不重不漏地经过每个点恰好一次。
输入格式
第一行输入整数 n。
接下来 n 行每行 n 个整数其中第 i 行第 j 个整数表示点 i 到 j 的距离记为 a[i,j]。
对于任意的 x,y,z数据保证 a[x,x]0a[x,y]a[y,x] 并且 a[x,y]a[y,z]≥a[x,z]。
输出格式
输出一个整数表示最短 Hamilton 路径的长度。
数据范围
1≤n≤20 0≤a[i,j]≤10^7
输入样例
5
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输出样例
18 AC代码
#includebits/stdc.h
using namespace std;const int N 20, M 1 N;
//使用二进制表示路过点的状态如00101表示走过3号点和1号点int f[M][N];
int w[N][N];//无向权图
int n;int main(){cin n;//输入for(int i 0; i n; i)for(int j 0; j n; j)cin w[i][j];//初始化memset(f, 0x3f, sizeof f); //题目为找最短长度初始化为无穷f[1][0] 0; //起点走过的路径长度为0for(int i 0; i 1 n; i)//枚举每一种状态for(int j 0; j n; j) //表示该状态是否经过j点if(i j 1)for(int k 0; k n; k)//计算经过j点前以k为终点的最短距离if(i k 1)f[i][j] min(f[i][j], f[i - (1 j)][k] w[k][j]);cout f[(1 n) - 1][n - 1] endl;;return 0;
}
