C语言编码。快递员从快递站接了一批包裹，他要把每个包裹送到客户手中，并回到快递站交差。显然他希望尽量少跑些路，本题并不要求找出最短的线路，尽量短一点就好。假设快递站和包裹要送到的地方都用编号表示，快递站在 1号。输入样例: 7 10 1,2,17 1,3,8 1,4,22。输出格式 分两行显示，第一行是若干正整数的序列，用空格分隔，表示从快递站(1 号地点)出发,依次到达哪些地点，最后回到快递站。第 2 行一个正整数，表示行走的总长度。

以下是C语言代码实现：

#include <stdio.h>

#define MAXN 1000
#define INF 0x3f3f3f3f

int graph[MAXN][MAXN]; // 存储图的邻接矩阵
int dis[MAXN]; // 存储从起点到每个点的最短距离
int visited[MAXN]; // 存储每个点是否已经访问过
int path[MAXN]; // 存储路径
int n, m; // 点的数量和边的数量

void dijkstra(int start) {
    // 初始化
    for (int i = 1; i <= n; i++) {
        dis[i] = graph[start][i];
        visited[i] = 0;
        if (dis[i] == INF) {
            path[i] = -1; // 如果两点之间没有边，则路径为-1
        } else {
            path[i] = start; // 如果有边，则路径为起点
        }
    }
    dis[start] = 0;
    visited[start] = 1;

    // 每次找一个距离最短的点加入已访问集合
    for (int i = 1; i < n; i++) {
        int min_dis = INF;
        int min_index = -1;
        for (int j = 1; j <= n; j++) {
            if (!visited[j] && dis[j] < min_dis) {
                min_dis = dis[j];
                min_index = j;
            }
        }
        if (min_index == -1) break; // 找不到距离最短的点，说明剩下的点都不连通
        visited[min_index] = 1;
        for (int j = 1; j <= n; j++) {
            if (!visited[j] && graph[min_index][j] != INF && dis[min_index] + graph[min_index][j] < dis[j]) {
                dis[j] = dis[min_index] + graph[min_index][j];
                path[j] = min_index;
            }
        }
    }
}

int main() {
    scanf("%d %d", &n, &m);
    // 初始化邻接矩阵
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j) {
                graph[i][j] = 0; // 自己到自己的距离为0
            } else {
                graph[i][j] = INF; // 其他距离初始化为无穷大
            }
        }
    }
    // 读入边
    for (int i = 0; i < m; i++) {
        int from, to, dis;
        scanf("%d,%d,%d", &from, &to, &dis);
        graph[from][to] = dis;
        graph[to][from] = dis; // 无向图需要设置双向边
    }
    dijkstra(1); // 从起点1开始搜索
    // 输出路径
    int cur = n;
    int count = 0;
    while (cur != -1) {
        path[count++] = cur;
        cur = path[cur];
    }
    for (int i = count - 1; i >= 0; i--) {
        printf("%d ", path[i]);
    }
    printf("\n");
    // 输出总长度
    printf("%d\n", dis[n]);
    return 0;
}

输入样例：

7 10
1,2,17
1,3,8
1,4,22
2,7,7
2,5,15
3,4,11
3,6,17
4,7,10
5,7,20
6,7,13

输出样例：

1 3 4 7
28