Se le da un gráfico completo no dirigido con N vértices. Todos menos los bordes K tienen un costo de A. Esos bordes K tienen un costo de B y los conoce (como una lista de pares). ¿Cuál es el costo mínimo del nodo 0 al nodo N - 1?

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

El problema es, obviamente, cuando esos bordes K cuestan más que los otros y el nodo 0 y el nodo N - 1 están conectados por un borde K.

Dijkstra no funciona. Incluso he intentado algo muy similar con un 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

El problema es que esto consume mucho tiempo debido al hecho de que para cada nodo tiene que hacer un bucle de 0 a N - 1 para encontrar los nodos adyacentes "buenos".

Alguien tiene mejores ideas? Gracias.

Editar: Aquí hay un enlace del concurso ACM:http://acm.ro/prob/probleme/B.pdf