某销售员要到n个城市去推销商品,已知各城市之间的路程(或旅费)s。售货员选定一条从驻地出发,经过每个城市一遍,最后回到驻地的路线,使得总的路程(或总旅费)最小。设G=(V,E)是一个带权图。图中的各边的费用(权)为正数。图中的一条周游路线是包括V中的每个顶点在内的一条回路。周游路线的费用是这条路线上所有边的费用之和。旅行售货员问题是指在图G中找出费用最小的周游路线。如果找不到可行方案,则输出-1。 输入 第一行城市的数量n。 接下来每行输入各城市之间的路程(旅费)。(假设起点即驻地为1号顶点) 输出 第一行最短路程(或最少旅费) 第二行最短路程(或费用最小)的周游路线 样例输入 Copy 4 1 2 30 1 3 6 1 4 4 2 3 5 2 4 10 3 4 20 样例输出 Copy 25 1 3 2 4 1 用C语言编写
时间: 2023-11-22 15:55:46 浏览: 18
```c
#include <stdio.h>
#define MAXN 20
#define INF 0x3f3f3f3f
int n, s[MAXN][MAXN], d[MAXN][1<<MAXN], p[MAXN][1<<MAXN];
int min(int a, int b) {
return a < b ? a : b;
}
int solve() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < (1 << n); j++) {
d[i][j] = INF;
}
}
d[0][1] = 0;
for (int S = 1; S < (1 << n); S++) {
for (int i = 0; i < n; i++) {
if ((S & (1 << i)) == 0) continue;
for (int j = 0; j < n; j++) {
if (i == j) continue;
if ((S & (1 << j)) == 0) continue;
if (d[j][S^(1<<j)] == INF) continue;
if (d[i][S] > d[j][S^(1<<j)] + s[j][i]) {
d[i][S] = d[j][S^(1<<j)] + s[j][i];
p[i][S] = j;
}
}
}
}
int ans = INF, last = 0;
for (int i = 1; i < n; i++) {
if (ans > d[i][(1<<n)-1] + s[i][0]) {
ans = d[i][(1<<n)-1] + s[i][0];
last = i;
}
}
printf("%d\n", ans);
int S = (1 << n) - 1;
int ans2[MAXN], len = 0;
while (S) {
ans2[len++] = last;
int temp = last;
last = p[last][S];
S ^= 1 << temp;
}
printf("1 ");
for (int i = len - 2; i >= 0; i--) {
printf("%d ", ans2[i] + 1);
}
printf("1\n");
return 0;
}
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &s[i][j]);
}
}
solve();
return 0;
}
```