您将获得一个包含N个顶点的完整无向图.除了K边之外的所有边都有A的成本.那些K边的成本为B,你知道它们(作为对的列表).从节点0到节点N-1的最低成本是多少.
2 <= N <= 500k
0 <= K <= 500k
1 <= A, B <= 500k
显然,问题是当那些K边缘比其他边缘花费更多并且节点0和节点N-1通过K边缘连接时.
Dijkstra不起作用.我甚至尝试过与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