• 问题描述 小哥从快递站接了一批包裹，他要把每个包裹送到客户手中，并回到快递站交差。显然，他希望尽量少跑些路，本题并不要求找出最短的线路，尽量短一点就好。假设快递站和包裹要送到的地方都用编号表示，快递站在1号，某些地点之间有道路相连，道路的长度已知。请为小哥设计一个送包裹的线路。比如：小哥接单的包裹要送往6个地点，各个地点之间是否有道路相通、以及路程长度如下图所示。• 输入格式 输入的第1行是两个整数，前一个数表示n的值，是包括出快递站在内的地点的数量，后一个表示m，即共有多少条道路。从第2行开始，每一行是3个正整数，用逗号分隔，形如“x，y，z”，表示两个地点之间道路长度，x和y是地点编号，z是长度。所有道路信息按首个地点x升序排列，x相同者再按y排序。• 输出格式 分两行显示，第一行是若干正整数的序列，用空格分隔，表示从快递站(1号地点)出发，依次到达哪些地点，最后回到快递站。第2行一个正整数，表示行走的总长度。• 数据范围 1≤n≤100 • 输入样例： 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 注： <1> 以上线路中需要从3号到4号送完包裹之后又回到3号 <2> 并不保证这是最短线路 用c++写一下

以下是用C++实现的代码，使用BFS遍历图：

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

const int N = 110;

int n, m;
vector<pair<int, int>> graph[N]; // 邻接表存储图
bool visited[N]; // 记录节点是否被访问过
int path[N]; // 记录遍历路径
int total_distance; // 记录总距离

void bfs(int start) {
    queue<int> q;
    q.push(start);
    visited[start] = true;
    path[0] = start;

    int idx = 1; // path数组的索引
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        for (auto& next : graph[cur]) {
            int neighbor = next.first;
            int distance = next.second;
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
                path[idx++] = neighbor;
                total_distance += distance;
            }
        }
    }

    // 回到起点
    path[idx] = start;
    total_distance += graph[path[idx - 1]][0].second;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b, c;
        scanf("%d,%d,%d", &a, &b, &c);
        graph[a].push_back({b, c});
        graph[b].push_back({a, c});
    }

    memset(visited, false, sizeof visited);
    bfs(1);

    // 输出结果
    for (int i = 0; i <= n; i++) {
        cout << path[i] << ' ';
    }
    cout << endl << total_distance << endl;

    return 0;
}

算法思路：

1. 读入输入，构建一个邻接表表示图。
2. 从起点1号开始，使用BFS遍历整个图，并记录遍历路径和总距离。
3. 遍历结束后，输出遍历路径和总距离。

时间复杂度：O(n+m)，其中n为节点数，m为边数。