为了解决机场连接问题，我们需要找到从起点区域到终点区域的最短路径。这个问题可以通过Dijkstra算法来解决，因为它适用于有权重的无向图，并且能够找到从一个节点到所有其他节点的最短路径

方法思路

1. 问题分析：我们需要找到从起点区域到终点区域的最短路径，每个区域可以看作图中的一个节点，道路可以看作节点之间的边，边有权重。
2. 算法选择：使用Dijkstra算法来解决这个问题，因为它适用于有权重的图，并且能够高效地找到最短路径。
3. 数据结构：使用邻接表来存储图的结构，邻接表由字典实现，键为节点，值为一系列的边和权重。
4. 实现步骤：
   • 读取输入数据,构建邻接表。
   • 初始化Dijkstra算法,使用优先队列来维护待处理的节点。
   • 每次从优先队列中取出距离最短的节点,更新其邻居的最短距离。
   • 记录每个节点的父节点,以便反溯路径。
   • 当找到终点节点时,使用父节点信息反溯路径并输出结果。

解决代码

import heapq
from collections import defaultdict
def main():
    # 读取道路信息
    graph = defaultdict(list)
    n = int(input())
    for _ in range(n):
        u, v, w = input().split()
        u = int(u)
        v = int(v)
        w = int(w)
        graph[u].append((v, w))
        graph[v].append((u, w))  # 假设道路是双向的
    s = int(input())
    e = int(input())
    if s == e:
        print("起点和终点相同，无需路径")
        return
    # 初始化Dijkstra算法
    distance = {}
    parent = {}
    distance[s] = 0
    heap = [(, s)]
    heapq.heapify(heap)
    found = False
    while heap:
        current_dist, u = heapq.heappop(heap)
        if u == e:
            found = True
            break
        if current_dist > distance.get(u, float('inf')):
            continue
        for v, w in graph[u]:
            if v not in distance or distance[v] > distance[u] + w:
                distance[v] = distance[u] + w
                parent[v] = u
                heapq.heappush(heap, (distance[v], v))
    if not found:
        print("从", s, "到", e, "无路径")
        return
    # 反溯路径
    path = []
    current = e
    while current != s:
        if current not in parent:
            break
        path.append(current)
        current = parent[current]
    if current != s:
        print("无路径")
        return
    # 反转路径，并添加起点
    path = [s] + path[::-1]
    print(" -> ".join(map(str, path)))
if __name__ == "__main__":
    main()

代码解释

• 读取输入：读取道路信息并构建邻接表，每行道路信息包含起点、终点和权重。
• 初始化：将起点的距离设为，并将其加入优先队列。
• Dijkstra算法：使用优先队列处理节点，更新每个节点的最短距离和父节点。
• 反溯路径：从终点节点开始，通过父节点信息反溯路径，得到从起点到终点的最短路径。
• 输出结果：如果存在路径，输出路径；否则，输出无路径信息。