【备战蓝桥杯系列】单源最短路径Dijkstra算法模板

Dijkstra算法模板

蓝���杯中也是会考到图论最短路的，一旦考到，基本是不会太难的，只要知道板子就基本能拿分了。

两个板子如下

朴素Dijkstra算法

适应情况：稠密图，正权边

时间复杂度 O(n^2 + m)

int dijkst(){    memset(dist, 0x3f, sizeof dist);//初始化成无穷大    dist[1] = 0;    for(int i = 1; i