给你一个完整的无向图,有 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
最佳答案
这是一项艰巨的案例工作:
- A < B 并且 0 和 N-1 由 A 加入 -> 平凡。
- B < A and 0 and N-1 joined by B -> trivial.
- B < A 并且 0 和 N-1 由 A 加入 -> 对只有 K 条边的图进行 BFS。
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) 时间内找到每个顶点的距离。
关于algorithm - 只有两种可能成本的完整图。从 0 到 N - 1 的最短路径成本是多少,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/23030181/