NOIP 普及 2014 第一轮 第 22 题：带权图中 A 到 E 的最短距离

题目

如图所示，图中每条边上的数字表示该边的长度，则从A到E的最短距离是。

答案

11

题解

考点定位

本题考「最短路手工求解」,对应大纲 4.3.3 最短路（难度【3】）。

解题过程

按原卷带权图从 A 出发 Dijkstra：逐点松弛后 E 的最短距离 = 11（沿 A→…→E 的最优链）。

答案：11。

易错提醒

① 手工 Dijkstra 表格化：每轮选定一点更新邻居；② 有向/无向、重边要看清。