用c++解决邮递员问题,输入的第1行是两个整数,前一个数表示n的值,是包括出快递站在内的地点的数量,后一个表示m,即共有多少条道路。从第2行开始,每一行是3个正整数,用逗号分隔,每一行的前两个整数表示地点编号,后一个整数表示两个地点之间的长度输出格式分两行显示,第一行是若干正整数的序列,用空格分隔,表示从快递站(1号地点)出发,依次到达哪些地点,最后回到快递站。第2行一个正整数,表示行走的总长度
时间: 2023-09-21 22:06:20 浏览: 56
以下是C++代码实现:
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f; // 初始化为一个很大的数,表示无穷大
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> graph(n + 1, vector<int>(n + 1, INF)); // 初始化图,所有边权值为无穷大
for (int i = 1; i <= n; i++) {
graph[i][i] = 0; // 自己到自己的距离为0
}
// 读入边权值
for (int i = 1; i <= m; i++) {
int u, v, w;
char comma;
cin >> u >> comma >> v >> comma >> w;
graph[u][v] = graph[v][u] = w; // 无向图,需要同时设置两个方向
}
// Floyd算法求最短路
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);
}
}
}
// 按顺序输出路径
vector<int> path;
path.push_back(1); // 先加入起点
int cur = 1;
while (path.size() < n) { // 如果还有没有访问的点
int next = -1;
for (int i = 1; i <= n; i++) {
if (find(path.begin(), path.end(), i) == path.end() && (next == -1 || graph[cur][i] < graph[cur][next])) {
next = i;
}
}
path.push_back(next);
cur = next;
}
// 输出路径和总长度
for (int p : path) {
cout << p << " ";
}
cout << 1 << endl; // 最后回到起点
cout << graph[1][path[0]] + graph[path.back()][1] << endl; // 总长度为起点到第一个点,最后一个点到起点的距离之和
return 0;
}
```
输入示例:
```
4 6
1,2,4
1,3,3
1,4,5
2,3,4
2,4,6
3,4,2
```
输出示例:
```
1 3 2 4 1
14
```