知识回顾:dijkstra
1. 定义ans[100000],ans[i]表示从起点到达i点的最小花费
2. 定义bool数组visit,visit[i]表示是否以点i为中心进行过出
边的松弛操作
3. ans[起点]=0,其余的赋值为inf
4. 定义一个pos变量,visit[pos]=1(访问过),表示现在的
位置,初始值为起点。
5. 列举所有与pos相联通的点,将这些点(i)的ans值更新:
ans[i]=min(ans[i],ans[pos]+到这些点需要的花费
6. 列举所有没有过的的点,找到ans值最小的点,赋值给
pos,visit[pos]=1(访问过)
7.所有点都访问过(visit[i]都==1),程序结束。此时,
ans[i]代表从起点到i的最短路径