NOIP 提高 2013 第一轮 第 14 题：与原数符号相反

题目

对一个 $n$ 个顶点、$m$ 条边的带权有向简单图用 Dijkstra 算法计算单源最短路时，如果不使用堆或其它优先队列进行优化，则其时间复杂度为（   ）。

选项

• A. $O(mn + n^3)$
• B. $O(n^2)$
• C. $O((m + n) \log n)$
• D. $O((m + n^2) \log n)$

答案

B

题解

考点定位

本题考「朴素 Dijkstra」,对应大纲 4.3.3 最短路（难度【2】）。

解题过程

无堆优化：每轮线性选点 O(n)×n 轮 = O(n²)。

选 B。

易错提醒

① 与 m 无关（邻接矩阵口径）；② 堆优化 O((n+m)log n)。