Você recebe um gráfico não direcionado completo com N vértices. Todas, exceto K arestas, têm um custo de A. Essas K arestas têm um custo de B e você as conhece (como uma lista de pares). Qual é o custo mínimo do nó 0 ao nó N-1.

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

O problema é, obviamente, quando essas arestas K custam mais do que as outras e o nó 0 e o nó N - 1 são conectados por uma aresta K.

Dijkstra não funciona. Eu até tentei algo muito semelhante com um 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

O problema é que isso consome muito tempo devido ao fato de que, para cada nó, é necessário fazer um loop de 0 a N-1 para encontrar os nós adjacentes "bons".

Alguém tem alguma idéia melhor? Obrigado.

Edit: Aqui está um link do concurso ACM:http://acm.ro/prob/probleme/B.pdf