Вам дан полный неориентированный граф с N вершинами. Все ребра, кроме K, имеют стоимость A. Эти ребра K имеют стоимость B, и вы их знаете (как список пар). Какова минимальная стоимость от узла 0 до узла N - 1.

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

Проблема, очевидно, заключается в том, что когда эти K ребер стоят дороже, чем другие, а узел 0 и узел N - 1 соединены K-ребром.

Дейкстра не работает. Я даже пробовал что-то очень похожее с 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, чтобы найти «хорошие» соседние узлы.

У кого-нибудь есть идеи получше? Спасибо.

Изменить: Вот ссылка с конкурса ACM:http://acm.ro/prob/probleme/B.pdf