HDU1874 – 畅通工程续

最短路模板:

  • Floyd 任意两点间的最短路,动态规划思想,$O(n^3)$
  • SPFA 单源最短路,Bellman-Ford的队列优化,通过进队出队进行松弛操作,可判断负环,$O(ke)$
  • Dijkstra 单源最短路,堆优化之后$O(e \log n)$

Floyd

SPFA

Dijkstra

 

说点什么

avatar
50
  Subscribe  
提醒