用C语言编程，基于Dijsktra算法的最短路径求解 描述：一张地图包括n个城市，假设城市间有m条路径（有向图），每条路径的长度已知。给定地图的一个起点城市和终点城市，利用Dijsktra算法求出起点到终点之间的最短路径。 输入：多组数据，每组数据有m+3行。第一行为两个整数n和m，分别代表城市个数n和路径条数m。第二行有n个字符，代表每个城市的名字。第三行到第m+2行每行有两个字符a和b和一个整数d，代表从城市a到城市b有一条距离为d的路。最后一行为两个字符，代表待求最短路径的城市起点和终点。当n和m都等于0时，输入结束。 输出：每组数据输出两行。第一行为一个整数，为从起点到终点之间最短路的长度。第二行为一串字符串，代表该路径。每两个字符之间用空格隔开。

以下是基于Dijsktra算法的最短路径求解的C语言代码：

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

#define MAXN 1001
#define INF 0x3f3f3f3f

int n, m;
int graph[MAXN][MAXN];
char city[MAXN][3];

int dijkstra(int start, int end, int *path)
{
    int i, j, k;
    int dist[MAXN], visited[MAXN], prev[MAXN];
    memset(visited, 0, sizeof(visited));
    memset(dist, INF, sizeof(dist));
    memset(prev, -1, sizeof(prev));
    for(i = 1; i <= n; i++) {
        dist[i] = graph[start][i];
        if(dist[i] < INF) prev[i] = start;
    }
    visited[start] = 1;
    for(i = 2; i <= n; i++) {
        int minDist = INF;
        for(j = 1; j <= n; j++) {
            if(!visited[j] && dist[j] < minDist) {
                k = j;
                minDist = dist[j];
            }
        }
        visited[k] = 1;
        if(k == end) break;
        for(j = 1; j <= n; j++) {
            if(!visited[j] && dist[k]+graph[k][j] < dist[j]) {
                dist[j] = dist[k] + graph[k][j];
                prev[j] = k;
            }
        }
    }
    if(prev[end] == -1) return INF;
    int count = 0;
    path[count++] = end;
    while(prev[path[count-1]] != -1) {
        path[count++] = prev[path[count-1]];
    }
    for(i = 0; i < count/2; i++) {
        int temp = path[i];
        path[i] = path[count-i-1];
        path[count-i-1] = temp;
    }
    return dist[end];
}

int main()
{
    while(1) {
        scanf("%d %d", &n, &m);
        if(n == 0 && m == 0) break;
        int i, j;
        memset(graph, INF, sizeof(graph));
        for(i = 1; i <= n; i++) {
            scanf("%s", city[i]);
            graph[i][i] = 0;
        }
        for(i = 1; i <= m; i++) {
            char a[3], b[3];
            int d;
            scanf("%s %s %d", a, b, &d);
            for(j = 1; j <= n; j++) {
                if(strcmp(a, city[j]) == 0) break;
            }
            int x = j;
            for(j = 1; j <= n; j++) {
                if(strcmp(b, city[j]) == 0) break;
            }
            int y = j;
            if(d < graph[x][y]) graph[x][y] = d;
        }
        char startCity[3], endCity[3];
        scanf("%s %s", startCity, endCity);
        int start, end;
        for(i = 1; i <= n; i++) {
            if(strcmp(startCity, city[i]) == 0) start = i;
            if(strcmp(endCity, city[i]) == 0) end = i;
        }
        int path[MAXN], len = dijkstra(start, end, path);
        if(len == INF) printf("From %s to %s: No path\n", startCity, endCity);
        else {
            printf("From %s to %s: %d\n", startCity, endCity, len);
            printf("%s", city[path[0]]);
            for(i = 1; i < len; i++) printf(" %s", city[path[i]]);
            printf("\n");
        }
    }
    return 0;
}

输入数据的格式为：

n m
city1 city2 ... cityn
a1 b1 d1
a2 b2 d2
...
am bm dm
startCity endCity

输出数据的格式为：

From startCity to endCity: len
path

其中，`len`为从起点到终点的最短距离，`path`为最短路径上的城市名字。如果不存在路径，则输出`No path`。