C++代码:从某地点出发,打卡所有点之后回到起点的经过地点序列,并求出所经历的路程
时间: 2024-03-17 17:45:46 浏览: 53
以下是一个基于动态规划的解决方案,可以求解小规模的TSP问题:
```c++
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN = 20;
const int INF = 0x3f3f3f3f;
int n, m;
int dist[MAXN][MAXN], dp[1 << MAXN][MAXN];
int tsp() {
memset(dp, INF, sizeof(dp));
dp[1][0] = 0;
for (int S = 1; S < (1 << n); S++) {
for (int i = 0; i < n; i++) {
if (S & (1 << i)) {
for (int j = 0; j < n; j++) {
if (S & (1 << j)) {
dp[S][i] = min(dp[S][i], dp[S ^ (1 << i)][j] + dist[j][i]);
}
}
}
}
}
return dp[(1 << n) - 1][0];
}
int main() {
cin >> n >> m;
memset(dist, INF, sizeof(dist));
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
dist[u][v] = dist[v][u] = w;
}
cout << tsp() << endl;
return 0;
}
```
其中`dist[i][j]`表示第i个点到第j个点的距离,`dp[S][i]`表示经过集合S中所有点,最后停留在第i个点的最短路程。