用c++编写邮递员问题,要求•输入样例: 7 10 1,2,17 1,3,8 1,4,22 2,5,13 3,4,8 3,6,20 4,5,9 4,7,19 5,7,12 6,7,16 •输出样例: 1 3 4 3 6 7 5 2 1 102
时间: 2023-07-02 14:08:02 浏览: 49
以下是邮递员问题的C++代码实现:
```c++
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10, M = 1 << N, INF = 0x3f3f3f3f;
int n, m;
int g[N][N], f[M][N];
string path[M][N];
int main()
{
cin >> n >> m;
memset(g, 0x3f, sizeof g);
for (int i = 0; i < m; i ++)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
g[a - 1][b - 1] = g[b - 1][a - 1] = min(g[a - 1][b - 1], c);
}
for (int i = 0; i < n; i ++) g[i][i] = 0;
for (int k = 0; k < n; k ++)
for (int i = 0; i < n; i ++)
for (int j = 0; j < n; j ++)
g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
memset(f, 0x3f, sizeof f);
f[1][0] = 0;
for (int i = 0; i < 1 << n; i += 2)
for (int j = 0; j < n; j ++)
if (i >> j & 1)
for (int k = 0; k < n; k ++)
if (k != j && (i >> k & 1))
if (f[i ^ 1 << j][k] + g[k][j] < f[i][j])
{
f[i][j] = f[i ^ 1 << j][k] + g[k][j];
path[i][j] = path[i ^ 1 << j][k] + to_string(j + 1) + " ";
}
cout << "1 ";
int u = (1 << n) - 1, v = 0;
for (int i = 0; i < n - 1; i ++)
{
int x = -1;
for (int j = 1; j < n; j ++)
if (!(u >> j & 1) && (x == -1 || f[u][j] + g[0][j] < f[u][x] + g[0][x]))
x = j;
cout << x + 1 << " ";
v += g[0][x];
u ^= 1 << x;
}
cout << "1 " << v << endl;
cout << path[(1 << n) - 1][0] << endl;
return 0;
}
```
代码中使用了状态压缩的方式,f[i][j]表示已经经过的节点集合为i,当前所在节点为j时,从当前节点出发,经过所有未经过的节点再回到起点的最小路径长度。path[i][j]表示已经经过的节点集合为i,当前所在节点为j时,从当前节点出发,经过所有未经过的节点再回到起点的最小路径。
首先,我们需要对输入的边进行处理,使用Floyd算法求出任意两点之间的最短路径。接下来,我们使用动态规划来解决问题。状态转移方程为:
$f[i][j]=\min_{k\ne j,k\in i}\{f[i\backslash \{j\}][k]+g[k][j]\}$
其中,i表示已经经过的节点集合,j表示当前所在的节点,k表示从i中除去j后剩余的节点。g[i][j]表示i到j的最短路径长度。
最终的答案为:从起点1开始,经过所有节点再回到1的最短路径长度,以及路径。
时间复杂度:$O(n^22^n)$
相关推荐
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)