任务描述 :一张地图包括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

以下是使用 Python 实现的代码：

import heapq

while True:
    n, m = map(int, input().split())
    if n == m == 0:
        break
    
    city_names = input().split()
    name_to_index = {name: i for i, name in enumerate(city_names)}
    
    edges = [[] for _ in range(n)]
    for _ in range(m):
        a, b, d = input().split()
        a_index, b_index = name_to_index[a], name_to_index[b]
        edges[a_index].append((b_index, int(d)))
    
    start, end = input().split()
    start_index, end_index = name_to_index[start], name_to_index[end]
    
    # 使用 Dijkstra 算法求最短路径
    distance = [float('inf')] * n
    distance[start_index] = 0
    prev = [-1] * n
    pq = [(0, start_index)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > distance[u]:
            continue
        for v, w in edges[u]:
            if distance[u] + w < distance[v]:
                distance[v] = distance[u] + w
                prev[v] = u
                heapq.heappush(pq, (distance[v], v))
    
    # 输出结果
    print(distance[end_index])
    path = []
    u = end_index
    while u != -1:
        path.append(city_names[u])
        u = prev[u]
    print(' '.join(path[::-1]))

在这个实现中，我们使用了 Python 的 heapq 模块来实现优先队列（堆）。其余部分的实现与上一篇回答类似。