C语言编码。小哥从快递站接了一批包裹，他要把每个包裹送到客户手中，并回到快递站交差。显然他希望尽量少跑些路，本题并不要求找出最短的线路，尽量短一点就好。假设快递站和包裹要送到的地方都用编号表示，快递站在 1号，某些地点之间有道路相连，道路的长度已知。请为小哥设计一个送包裹的线路。比如:小哥接单的包裹要送往 6 个地点输入格式 输入的第 1行是两个整数，前一个数表示 n 的值，是包括出快递站在内的地点的数量后一个表示 m，即共有多少条道路。从第 2 行开始，每一行是 3 个正整数，用逗号分隔，形如“x,,z”，表示两个地点之间道路长度，x 和y是地点编号，z 是长度。所有道路信息按首个地点x 升序排列，x 相同者再按V排序。 输出格式 分两行显示，第一行是若干正整数的序列，用空格分隔，表示从快递站(1 号地点)出发,依次到达哪些地点，最后回到快递站。第 2 行一个正整数，表示行走的总长度。邻接矩阵

#include <stdio.h>
#include <stdlib.h>

#define MAXN 100 // 最大地点数量

int n, m;
int graph[MAXN][MAXN]; // 道路长度矩阵

void dijkstra(int start, int end, int path[], int *length) {
    int visited[MAXN] = { 0 }; // 记录已访问的结点
    int dist[MAXN]; // 记录起点到每个结点的最短距离
    int prev[MAXN]; // 记录最短路径中每个结点的前一个结点

    // 初始化
    for (int i = 0; i < n; i++) {
        dist[i] = graph[start][i];
        if (dist[i] != -1) {
            prev[i] = start;
        }
    }
    visited[start] = 1;

    // 求解最短路径
    for (int i = 1; i < n; i++) {
        int min_dist = -1;
        int u = -1;
        // 找到未访问结点中距离起点最近的结点
        for (int j = 0; j < n; j++) {
            if (!visited[j] && dist[j] != -1) {
                if (min_dist == -1 || dist[j] < min_dist) {
                    min_dist = dist[j];
                    u = j;
                }
            }
        }
        if (u == -1) {
            break; // 所有结点都已访问过
        }
        visited[u] = 1;
        // 更新未访问结点的最短距离和前一个结点
        for (int v = 0; v < n; v++) {
            if (!visited[v] && graph[u][v] != -1) {
                if (dist[v] == -1 || dist[u] + graph[u][v] < dist[v]) {
                    dist[v] = dist[u] + graph[u][v];
                    prev[v] = u;
                }
            }
        }
    }

    // 生成路径
    int index = 0;
    path[index++] = end;
    while (prev[path[index-1]] != start) {
        path[index++] = prev[path[index-1]];
    }
    path[index++] = start;

    *length = dist[end];
}

int main() {
    // 读入地点数量和道路数量
    scanf("%d%d", &n, &m);

    // 初始化道路长度矩阵
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            graph[i][j] = -1;
        }
    }

    // 读入道路信息
    for (int i = 0; i < m; i++) {
        int u, v, w;
        scanf("%d,%d,%d", &u, &v, &w);
        graph[u-1][v-1] = graph[v-1][u-1] = w;
    }

    // 求解路径
    int path[MAXN];
    int length;
    dijkstra(0, 0, path, &length);

    // 输出路径
    for (int i = n-1; i >= 0; i--) {
        printf("%d ", path[i]+1);
    }
    printf("\n%d\n", length);

    return 0;
}