algorithm - Complete graph with only two possible costs. What's the shortest path's cost from 0 to N - 1

Question

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 

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 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

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.

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

Answer 1

This is laborous case work:

1. A < B and 0 and N-1 are joined by A -> trivial.
2. B < A and 0 and N-1 are joined by B -> trivial.
3. B < A and 0 and N-1 are joined by A -> Do BFS on graph with only K edges.

4. 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).

   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.