C语言编码。快递员从快递站接了一批包裹，他要把每个包裹送到客户手中，并回到快递站交差。假设快递站和包裹要送到的地方都用编号表示，快递站在 1号。输入格式 输入的第 1行是两个整数，前一个数表示 n 的值，是包括出快递站在内的地点的数量后一个表示 m，即共有多少条道路。从第 2 行开始，每一行是 3 个正整数，用逗号分隔，形如“x,,z”，表示两个地点之间道路长度，x 和y是地点编号，z 是长度。所有道路信息按首个地点x 升序排列，x 相同者再按V排序。 输出格式 分两行显示，第一行是若干正整数的序列，用空格分隔，表示从快递站(1 号地点)出发,依次到达哪些地点，最后回到快递站。第 2 行一个正整数，表示行走的总长度。

以下是C语言代码实现，其中用了邻接表存储图：

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

#define MAXN 1000    // 最大地点数
#define INF 0x3f3f3f3f    // 无穷大

// 图的邻接表存储结构
typedef struct node {
    int v;    // 目标地点编号
    int w;    // 边的权值
    struct node *next;    // 指向下一个邻接点的指针
} Node;

Node *graph[MAXN];    // 图的邻接表
int dist[MAXN];    // 距离数组，dist[i] 表示从快递站到 i 号地点的最短距离
int path[MAXN];    // 路径数组，path[i] 表示从快递站到 i 号地点的路径上 i 的前一个地点

int n, m;    // 地点数和道路数

// 添加一条边
void addEdge(int u, int v, int w) {
    Node *p = (Node *) malloc(sizeof(Node));
    p->v = v;
    p->w = w;
    p->next = graph[u];
    graph[u] = p;
}

// Dijkstra 算法求最短路径
void dijkstra() {
    int visited[MAXN] = {0};    // 记录已访问的地点
    dist[1] = 0;    // 初始状态：快递站到自身的距离为0
    visited[1] = 1;    // 标记快递站已经访问过了

    // 初始化距离数组和路径数组
    for (int i = 2; i <= n; i++) {
        dist[i] = INF;
        path[i] = -1;
    }

    // 循环 n-1 次，每次找到一个最短路径上的新地点
    for (int i = 1; i < n; i++) {
        int minDist = INF;
        int u = -1;
        // 找到未访问过的距离最小的地点
        for (int j = 1; j <= n; j++) {
            if (!visited[j] && dist[j] < minDist) {
                minDist = dist[j];
                u = j;
            }
        }
        if (u == -1) {
            break;    // 如果没有找到新地点，说明剩下的地点都不连通
        }
        visited[u] = 1;    // 标记 u 已经访问过了

        // 更新与 u 相邻的地点的距离
        Node *p = graph[u];
        while (p != NULL) {
            int v = p->v;
            int w = p->w;
            if (!visited[v] && dist[u] + w < dist[v]) {    // 如果 v 未访问过且从快递站到 v 的距离可以通过 u 走得更短
                dist[v] = dist[u] + w;
                path[v] = u;
            }
            p = p->next;
        }
    }
}

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

    // 初始化邻接表
    for (int i = 1; i <= n; i++) {
        graph[i] = NULL;
    }

    // 读入道路信息，建图
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        scanf("%d,%d,%d", &u, &v, &w);
        addEdge(u, v, w);
    }

    // 运行 Dijkstra 算法求最短路径
    dijkstra();

    // 输出路径
    printf("1 ");
    for (int i = 2; i <= n; i++) {
        printf("%d ", i);
    }
    printf("1\n");

    // 输出路径长度
    printf("%d\n", dist[1] * 2);

    return 0;
}