您将得到一个完整的无向图有n个顶点。但所有k条边有A的成本那些k条边有B的成本，你认识他们（成对列表）。什么是最小的代价从节点0到节点N - 1

You are given a complete undirected graph with N vertices. All but K edges have a cost of A. Those K edges have a cost of B and you know them (as a list of pairs). What's the minimum cost from node 0 to node N - 1.

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

的问题是，很明显，当那些k条边成本比其他的和节点0和节点N - 1由K边缘连接

The problem is, obviously, when those K edges cost more than the other ones and node 0 and node N - 1 are connected by a K-edge.

Dijkstra算法是行不通的。我甚至尝试了一个BFS非常相似。

Dijkstra doesn't work. I've even tried something very similar with a 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，以便找到好的相邻节点

The problem is that this uses up a lot of time due to the fact that for every node you have to make a loop from 0 to N - 1 in order to find the "good" adjacent nodes.

没有人有任何更好的想法？谢谢你。

Does anyone have any better ideas? Thank you.

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

Here is a link from the ACM contest: http://acm.ro/prob/probleme/B.pdf

推荐答案

这是laborous情况下工作：

This is laborous case work:

A＆LT; B和0和N-1是由乙接合 - > 您可以检查在O（N）的时间是有长度为2 *一个路径（尝试在中间的每一个顶点）。 A < B and 0 and N-1 are joined by A -> trivial. B < A and 0 and N-1 are joined by B -> trivial. B < A and 0 and N-1 are joined by A -> Do BFS on graph with only K edges.

A < B and 0 and N-1 are joined by B -> You can check in O(N) time is there is a path with length 2*A (try every vertex in middle).

要检查其他路径长度以下的算法应该做的伎俩： 设x（D）采用ð短边从0开始，您可以使用下面的算法发现X（D）设置节点进行访问：取每个顶点v与未知的远方和iterativelly检查V和顶点之间的边从X（D-1 ）。如果您发现了短边，则v是X（D），否则你踩到长边。因为有最多有K长边可以至多K次踩在他们身上。所以，你应该找到距离的每一个顶点在大多数O（N + K）的时间。

To check other path lengths following algorithm should do the trick: Let X(d) be set of nodes reachable by using d shorter edges from 0. You can find X(d) using following algorithm: Take each vertex v with unknown distance and iterativelly check edges between v and vertices from X(d-1). If you found short edge, then v is in X(d) otherwise you stepped on long edge. Since there are at most K long edges you can step on them at most K times. So you should find distance of each vertex in at most O(N + K) time.