Complete graph with only two possible costs. What&

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.

Answer 2

As you have correctly noted, the problem comes when A > B and edge from 0 to n-1 has a cost of A.

In this case you can simply delete all edges in the graph that have a cost of A. This is because an optimal route shall only have edges with cost B.

Then you can perform a simple BFS since the costs of all edges are the same. It will give you optimal performance as pointed out by this link: Finding shortest path for equal weighted graph

Moreover, you can stop your BFS when the total cost exceeds A.

Answer 3

I propose a solution to a somewhat more general problem where you might have more than two types of edges and the edge weights are not bounded. For your scenario the idea is probably a bit overkill, but the implementation is quite simple, so it might be a good way to go about the problem.

You can use a segment tree to make Dijkstra more efficient. You will need the operations

• set upper bound in a range as in, given U, L, R; for all x[i] with L <= i <= R, set x[i] = min(x[i], u)
• find a global minimum

The upper bounds can be pushed down the tree lazily, so both can be implemented in O(log n)

When relaxing outgoing edges, look for the edges with cost B, sort them and update the ranges in between all at once.

The runtime should be O(n log n + m log m) if you sort all the edges upfront (by outgoing vertex).

EDIT: Got accepted with this approach. The good thing about it is that it avoids any kind of special casing. It's still ~80 lines of code.

Answer 4

In the case when A < B, I would go with kind of a BFS, where you would check where you can't reach instead of where you can. Here's the pseudocode:

G(k) is the set of nodes reachable by k cheap edges and no less. We start with G(0) = {v0}

while G(k) isn't empty and G(k) doesn't contain vN-1 and k*A < B
  A = array[N] of zeroes
  for every node n in G(k)
    for every expensive edge (n,m)
      A[m]++
  # now we have that A[m] == |G(k)| iff m can't be reached by a cheap edge from any of G(k)
  set G(k+1) to {m; A[m] < |G(k)|} except {n; n is in G(0),...G(k)}
  k++

This way you avoid iterating through the (many) cheap edges and only iterate through the relatively few expensive edges.