只有两种可能的成本的完整图.从 0 到 N - 1 的最短路径的成本是多少 [英] Complete graph with only two possible costs. What's the shortest path's cost from 0 to N - 1

问题描述

给定一个有 N 个顶点的完整无向图.除了 K 条边之外，所有边的成本都是 A.那些 K 条边的成本是 B，你知道它们(作为对的列表).从节点 0 到节点 N - 1 的最小成本是多少.

You are given a complete undirected graph with N vertices. All but K edges have a cost of A. Those K edges have a cost of B and you know them (as a list of pairs). What's the minimum cost from node 0 to node N - 1.

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

问题很明显，当这 K 条边的成本高于其他边，并且节点 0 和节点 N - 1 由 K 边连接时.

The problem is, obviously, when those K edges cost more than the other ones and node 0 and node N - 1 are connected by a K-edge.

Dijkstra 不起作用.我什至尝试过与 BFS 非常相似的东西.

Dijkstra doesn't work. I've even tried something very similar with a 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 的循环才能找到好的"相邻节点.

The problem is that this uses up a lot of time due to the fact that for every node you have to make a loop from 0 to N - 1 in order to find the "good" adjacent nodes.

有人有更好的想法吗?谢谢.

Does anyone have any better ideas? Thank you.

这是 ACM 竞赛的链接:http://acm.ro/prob/probleme/B.pdf

Here is a link from the ACM contest: http://acm.ro/prob/probleme/B.pdf

推荐答案

这是一个繁重的案例工作:

This is laborous case work:

1. A 平凡.
2. B 平凡.
3. B 连接对只有 K 条边的图进行 BFS.

4. A 您可以检查 O(N) 时间是否存在长度为 2*A 的路径(尝试中间的每个顶点).

1. A < B and 0 and N-1 are joined by A -> trivial.
2. B < A and 0 and N-1 are joined by B -> trivial.
3. B < A and 0 and N-1 are joined by A -> Do BFS on graph with only K edges.

4. A < B and 0 and N-1 are joined by B -> You can check in O(N) time is there is a path with length 2*A (try every vertex in middle).

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

To check other path lengths following algorithm should do the trick: Let X(d) be set of nodes reachable by using d shorter edges from 0. You can find X(d) using following algorithm: Take each vertex v with unknown distance and iterativelly check edges between v and vertices from X(d-1). If you found short edge, then v is in X(d) otherwise you stepped on long edge. Since there are at most K long edges you can step on them at most K times. So you should find distance of each vertex in at most O(N + K) time.

这篇关于只有两种可能的成本的完整图.从 0 到 N - 1 的最短路径的成本是多少的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！