题目描述

蓝桥王国中有 N 个城市，编号从 1 到 N，王国首都是 1 号城市。国王需要知道从首都到每个城市的最短距离。

给定 M 条有向道路，每条道路连接两个城市 u 和 v，长度为 w。如果某个城市从首都不可达，则输出 -1。

解题方法：Dijkstra 堆优化

标准的单源最短路问题，所有边权非负，直接使用 Dijkstra 堆优化求解。从起点（首都）出发，用优先队列不断松弛邻边，最终得到所有节点的最短距离。

代码解析

import os
import sys
from collections import defaultdict
import heapq

N, M = map(int, input().split())

# 邻接表建图
g = defaultdict(list)
for _ in range(M):
    u, v, w = map(int, input().split())
    g[u-1].append((v-1, w))   # 转为 0 索引

dist = [float('inf')] * N
dist[0] = 0
pq = [(0, 0)]

while pq:
    d, u = heapq.heappop(pq)
    if d > dist[u]:
        continue
    for v, w in g[u]:
        nd = d + w
        if nd < dist[v]:
            dist[v] = nd
            heapq.heappush(pq, (nd, v))

# 输出结果，不可达输出 -1
ans = []
for i in range(N):
    ans.append(dist[i] if dist[i] != float('inf') else -1)
print(*ans)

代码要点说明

  • 建图：输入编号从 1 开始，转为 0 索引使用。defaultdict(list) 处理稀疏图更高效。
  • 队列初始化：起点距离 0，压入 pq。
  • 结果输出：dist[i] 仍为 inf 表示不可达，替换为 -1。
  • 核心逻辑与标准 Dijkstra 堆优化完全一致。

复杂度分析

  • 时间复杂度：O((N + M)log N)，N 为城市数，M 为道路数。
  • 空间复杂度：O(N + M)，邻接表存储图需要 O(M) 空间，dist 数组和堆需要 O(N) 空间。