只有两个可能成本的完整图形。从0到N-1的最短路径成本是多少

只有两个可能成本的完整图形。从0到N-1的最短路径成本是多少

这是费力的案例工作：

1. A

   <B和0和N-1通过A->

   琐碎连接。
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的路径（尝试中间的每个顶点）。

要检查其他路径长度，可以使用以下算法来达到目的：通过从0开始使用d个较短的边，使X（d）成为可到达的节点集。您可以使用以下算法找到X（d）：取每个未知距离且迭代的顶点v从X（d-1）检查v和顶点之间的边。如果发现短边，则v在X（d）中，否则踩长边。由于最多有K个长边，因此您最多可以踩K次。因此，您应该在最多O（N+ K）的时间内找到每个顶点的距离。