您将获得具有N个顶点的完整无向图。除K边以外的所有边的成本为A。您知道K边（作为对的列表）的成本为B。从节点0到节点N-1的最低成本是多少？

2 <= N <= 500k
0 <= K <= 500k
1 <= A, B <= 500k

问题显然是，当那些K边缘的成本高于其他K边缘，并且节点0和节点N-1通过K边缘连接时。

Dijkstra不起作用。我什至尝试过使用BFS进行类似的操作。

Step1: Let G(0) be the set of "good" adjacent nodes with node 0.
Step2: For each node in G(0):
              compute G(node)
              if G(node) contains N - 1
                  return step

              else
                  add node to some queue
       repeat step2 and increment step

问题在于，由于要发现每个“节点”必须从0到N-1进行循环才能找到“良好”的相邻节点，因此这会花费大量时间。

有谁有更好的主意吗？谢谢。

编辑：这是ACM竞赛的链接：http :
//acm.ro/prob/probleme/B.pdf