SS's Trace

Sirius's Blog

Luogu P1339 - 单源最短路

PROBLEM

https://www.luogu.org/problemnew/show/P1339

ANALYSIS

裸题 ,保存模板

时间复杂度:

  • SPFA O(k*E)  , k 为每个节点进入队列的次数,一般小于等于2,最坏情况为O(V*E)
  • Dijkstra(Heap) O(2*E+V*lgV)
  • Dijkstra(Ordinary) O(n^2)

SOLUTION

 

CC BY-NC-SA 4.0 本作品使用基于以下许可授权:Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注