题解 | 无人机物流网络最优路径规划

import sys
import heapq
from collections import defaultdict
N, K = map(int, sys.stdin.readline().split())
data = list(map(int, sys.stdin.read().split()))

adj = defaultdict(lambda : [])
for k in range(K):
    u, v, w = data[(3*k): (3*k +3)]
    adj[u].append((v, w))
    adj[v].append((u, w))
s, e = data[-2:]

INF = 0x3F3F3F3F
def dijkstra(s):
    q = [(0, s)]
    dists = defaultdict(lambda: INF)
    dists[s] = 0
    vis = set()
    while q:
        d, node = heapq.heappop(q)
        if node in vis:
            continue
        vis.add(node)
        for c, w in adj[node]:
            if dists[c] > d + w:
                heapq.heappush(q, (d + w, c))
                dists[c] = d + w
    return dists
# 从终点倒着更新，这样可以方便寻找起点的下一跳
dists = dijkstra(e)
if dists[s] >= INF:
    print(-1)
    print(-1)
    exit(0)
n_jump = []
for c, w in adj[s]:
    if dists[c] + w == dists[s]:
        n_jump.append(c)
print(dists[s])
print(' '.join(map(str, n_jump)))

1. 从终点进行一次dijkstra算法即可
2. 扫描起点的后继节点，判断哪些是符合最短路