This question already has answers here:
（4个答案）
我有一个有n个顶点的完整图，我需要找到从给定源到给定目标的最短路径。所有的边都有初始代价a，那么对于k个边，代价将变为b。在顶点1和顶点n之间找到最小代价的最佳方法是什么[算法在顶点1和顶点n之间找到最小代价（即最短路径]？输入是nkab和k个边（带成本b的边）。
哪里：
2 <= N <= 500000
0 <= K <= 500000
1 <= A, B <= 500000
我试过用Dijkstra，但花了很长时间~2分钟，我需要像2秒这样的东西。
最佳答案
如果1和N之间的边的成本是A。
1）如果A<B，则最低成本为A。
2）如果A>B，则使用BFS查找从1到N的最少跳数，仅通过代价B的边。假设L和1之间至少有N边，然后返回min(LB,A)。这是典型的BFS，成本是O(N+K)。
如果1和N之间的边是B。
1）如果“A>B”，则答案为B。
2）仅使用成本1的边查找从N到A的最少跳数。设S[h]为h跳可到达的顶点集，而S'为尚未到达的顶点集，则可解如下。min_dis() { S[0] = {1}; int h = 0; S'={2,...,N}; while (S[h] is not empty) { S[h+1] = {}; for_each (v1 in S'){ for (v2 in S[h]) { if (cost[v1][v2] == A) { S[h+1].insert(1); S'.remove(v1); if (v1 == N) return min((h+1)*A, B); break; } } } h++; } return B; }
我们可以证明这个算法也是O(N+K)，因为每次测试const[v1][v2]==A都是true，所以S'的大小将减少1，并且当这个测试是K时最多有false个时间，因为最多有K个带成本的边B。所以它保证完成O(N+K)
总的来说，算法是O(N+K)，这将保证2sec时间限制。
关于algorithm - 完整图中两个顶点之间的最短路径，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/23097471/