Luogu P1339 – 单源最短路

  • 2018-11-29
  • 194
  • 0
  • 0

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.

评论

还没有任何评论,你来说两句吧