用c++解决邮递员问题。输入的第1行是两个整数,前一个数表示n的值,是包括出快递站在内的地点的数量,后一个表示m,即共有多少条道路。从第2行开始,每一行是3个正整数,用逗号分隔,每一行的前两个整数表示地点编号,后一个整数表示两个这两个地点之间的长度。每个地点编号可以重复经过。求出最短路径。出格式分两行显示,第一行是若干正整数的序列,用空格分隔,表示从快递站(1号地点)出发,依次到达哪些地点,最后回到快递站。第2行一个正整数,表示行走的总长度
时间: 2023-09-26 15:06:41 浏览: 76
以下是C++代码实现:
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
int n, m;
int d[1 << 20][20]; // d[S][i]表示经过S集合中所有点,以i为终点的最短距离
int p[1 << 20][20]; // p[S][i]表示从i出发,经过S集合中所有点,到达i的前一个点
vector<pair<int, int>> adj[20]; // 邻接表
// TSP算法
int tsp() {
for (int S = 1; S < (1 << n); ++S) {
for (int i = 0; i < n; ++i) {
d[S][i] = INF;
p[S][i] = -1;
}
}
d[1][0] = 0;
for (int S = 1; S < (1 << n); ++S) {
for (int i = 0; i < n; ++i) {
if (!(S & (1 << i))) continue;
for (auto& e : adj[i]) {
int j = e.first, cost = e.second;
if (!(S & (1 << j))) continue;
if (d[S][j] > d[S ^ (1 << j)][i] + cost) {
d[S][j] = d[S ^ (1 << j)][i] + cost;
p[S][j] = i;
}
}
}
}
int ans = INF, last = -1;
for (int i = 0; i < n; ++i) {
if (ans > d[(1 << n) - 1][i] + adj[i][0].second) {
ans = d[(1 << n) - 1][i] + adj[i][0].second;
last = i;
}
}
vector<int> path;
int S = (1 << n) - 1, cur = last;
while (cur != -1) {
path.push_back(cur + 1);
int next = p[S][cur];
S ^= (1 << cur);
cur = next;
}
path.push_back(1);
reverse(path.begin(), path.end());
for (int i = 0; i < path.size(); ++i) {
if (i > 0) cout << " ";
cout << path[i];
}
cout << endl << ans << endl;
}
int main() {
cin >> n >> m;
for (int i = 0; i < m; ++i) {
int u, v, w;
char c;
cin >> u >> c >> v >> c >> w;
adj[u - 1].push_back({v - 1, w});
adj[v - 1].push_back({u - 1, w});
}
tsp();
return 0;
}
```
思路解析:
这里采用状态压缩DP来求解TSP问题。定义状态 $d[S][i]$ 表示经过集合 $S$ 中所有点,以 $i$ 为终点的最短路径长度。由于 $S$ 最多包含 $n$ 个点,因此状态数为 $2^n \times n$。转移方程为:
$$
d[S][i] = \min\{d[S \setminus \{j\}][j] + w_{ji}\} \quad (j \in S, j \neq i)
$$
其中 $S \setminus \{j\}$ 表示把 $j$ 从 $S$ 中删除的操作,$w_{ji}$ 表示从 $j$ 到 $i$ 的距离。这里需要注意的是,每次更新 $d[S][i]$ 时,需要同时记录下来从 $i$ 到达 $j$ 的前一个点 $p[S][i]$,以便最后回溯路径。
求解完所有状态后,从所有以 $i$ 为终点的路径中选取一条最短路径,即:
$$
\min\{d[(1<<n)-1][i] + w_{i0}\} \quad (0 \leq i < n)
$$
其中 $w_{i0}$ 表示从 $i$ 到起点 $0$ 的距离。最后回溯路径即可。
时间复杂度为 $O(n^22^n)$,空间复杂度为 $O(n2^n)$,可以通过本题。