Luogu P3371 【模板】单源最短路径

最短路的模板题。。。 SPFA打过一遍。 但今天终于看懂了Dijkstra和堆优化，走一发。 Dijkstra的思想很简单，每次找到和起点dis最小的点，再将该点到其他有边相连的点的dis更新。重复n次即可。记得判断哪个点用过。 裸Dijkstra复杂度为O（n^2），但对于10000的数据能跑90
posted @ 2017-11-28 18:57  空気力学の詩  阅读(208)  评论(0)  编辑  收藏  举报