任务描述 :一张地图包括n个城市，假设城市间有m条路径（有向图），每条路径的长度已知。给定地图的一个起点城市和终点城市，利用Dijsktra算法求出起点到终点之间的最短路径。编程要求 输入 多组数据，每组数据有m+3行。第一行为两个整数n和m，分别代表城市个数n和路径条数m。第二行有n个字符，代表每个城市的名字。第三行到第m+2行每行有两个字符a和b和一个整数d，代表从城市a到城市b有一条距离为d的路。最后一行为两个字符，代表待求最短路径的城市起点和终点。当n和m都等于0时，输入结束。 输出 每组数据输出两行。第一行为一个整数，为从起点到终点之间最短路的长度。第二行为一串字符串，代表该路径。每两个字符之间用空格隔开。 测试说明 平台会对你编写的代码进行测试： 测试输入： 3 3 A B C A B 1 B C 1 A C 3 A C 6 8 A B C D E F A F 100 A E 30 A C 10 B C 5 C D 50 E D 20 E F 60 D F 10 A F 0 0 预期输出： 2 A B C 60 A E D F用C语言生成代码

以下是使用 C 语言实现的代码：

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

#define MAX_N 100
#define INF 0x3f3f3f3f

int n, m;
char city_names[MAX_N][3];
int name_to_index[MAX_N];
int edges[MAX_N][MAX_N];
char start[3], end[3];

void dijkstra(int start_index, int end_index, int distance[], int prev[]) {
    int visited[MAX_N] = {0};
    distance[start_index] = 0;
    prev[start_index] = -1;
    for (int i = 0; i < n; i++) {
        int u = -1;
        for (int j = 0; j < n; j++) {
            if (!visited[j] && (u == -1 || distance[j] < distance[u])) {
                u = j;
            }
        }
        if (u == -1 || u == end_index) {
            break;
        }
        visited[u] = 1;
        for (int v = 0; v < n; v++) {
            if (!visited[v] && edges[u][v] != INF && distance[u] + edges[u][v] < distance[v]) {
                distance[v] = distance[u] + edges[u][v];
                prev[v] = u;
            }
        }
    }
}

void print_path(int start_index, int end_index, int prev[]) {
    char path[MAX_N * 3] = "";
    int path_index = 0;
    int u = end_index;
    while (u != -1) {
        path_index += sprintf(path + path_index, "%s ", city_names[u]);
        u = prev[u];
    }
    path[path_index - 1] = '\0';
    printf("%s\n", path);
}

int main() {
    while (scanf("%d %d", &n, &m) == 2 && n != 0 && m != 0) {
        for (int i = 0; i < n; i++) {
            scanf("%s", city_names[i]);
            name_to_index[city_names[i][0] - 'A'] = i;
        }
        memset(edges, INF, sizeof(edges));
        for (int i = 0; i < m; i++) {
            char a[3], b[3];
            int d;
            scanf("%s %s %d", a, b, &d);
            int a_index = name_to_index[a[0] - 'A'];
            int b_index = name_to_index[b[0] - 'A'];
            edges[a_index][b_index] = d;
        }
        scanf("%s %s", start, end);
        int start_index = name_to_index[start[0] - 'A'];
        int end_index = name_to_index[end[0] - 'A'];
        int distance[MAX_N], prev[MAX_N];
        memset(distance, INF, sizeof(distance));
        dijkstra(start_index, end_index, distance, prev);
        printf("%d ", distance[end_index]);
        print_path(start_index, end_index, prev);
    }
    return 0;
}

在这个实现中，我们使用了两个数组 `distance` 和 `prev` 分别记录起点到各个城市的距离和最短路径中每个城市的前一个城市。我们也可以使用一个优先队列来实现 Dijkstra 算法，这样可以减少时间复杂度。但是为了代码的简洁，我们在这里使用了简单的选择排序来选择未访问过的距离最小的城市。