只有两个可能的成本的完整图表.什么是从0到N-1的最短路径成本

Question

您将获得一个包含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

Answer 1

这是一项费力的案例工作：

1. A < B 且 0 和 N-1 通过 A -> trivial 连接。
2. B < A 且 0 和 N-1 通过 B -> 平凡连接。
3. B < A 且 0 和 N-1 由 A 连接 -> 在只有 K 条边的图上进行 BFS。

4. A < B 且 0 和 N-1 由 B 连接 -> 您可以在 O(N) 时间内检查是否存在长度为 2*A 的路径（尝试中间的每个顶点）。

   要检查其他路径长度，以下算法应该可以解决问题：让 X(d) 是通过使用从 0 开始的 d 个较短边可到达的节点集。您可以使用以下算法找到 X(d)：以未知距离迭代每个顶点 v检查 v 和 X(d-1) 顶点之间的边。如果你发现了短边，那么 v 在 X(d) 中，否则你踩到了长边。由于最多有 K 个长边，因此您最多可以踩到它们 K 次。所以你应该在最多 O(N + K) 时间内找到每个顶点的距离。