算法

Hailin

蓝桥杯 蓝桥国王

题目描述蓝桥王国中有 N 个城市，编号从 1 到 N，王国首都是 1 号城市。国王需要知道从首都到每个城市的最短距离。给定 M 条有向道路，每条道路连接两个城市 u 和 v，长度为 w。如果某个城市从首都不可达，则输出 -1。解题方法：Dijkstra 堆优化标准的单源最短路问题，所有边权非负，直接使用 Dijkstra 堆优化求解。从起点（首都）出发，用优先队列不断松弛邻边，最终得到所有节点的最

算法

Hailin

Dijkstra 堆优化版

题目描述给定一个有向带权图，求从起点到所有其他节点的最短路径长度。图中可能存在重边和自环，边权为正数。Dijkstra 算法适用于所有边权非负的图。堆优化版本通过优先队列（最小堆）快速取出当前距离最小的未确定节点，将时间复杂度从 O(V²) 优化到 O((V + E)log V)。解题方法：Dijkstra + 堆优化算法思路维护一个距离数组 dist，初始时起点距离为 0，其余为无穷大。用最小堆