是否可以在具有循环和负边的无向图中使用 BFS（使用遍历的最小顶点）在 O(log n) 时间内从源中找到目的地？
例如：给定一个具有 N 个顶点和 N 个边的简单连通图 G（一个简单图是一个无向图，它没有环，并且在任何两个不同顶点之间不超过一条边）。很明显，图 G 恰好包含一个循环，您可以假设这个循环的长度是奇数（这个循环中有奇数个顶点）。顶点从 1 到 N 编号。每条边都分配有相应的整数权重。你的任务是激发两种类型的查询： 更新由 fuv 表示的查询：将最短路径上所有边权重的符号从顶点 u 更改为顶点（稍后可以在这个问题中看到最短路径的定义） v. 查找由 ? 表示的查询 uv：在从顶点u到顶点v的最短路径上，找到（可能是空的）连续边集，使得权重之和最大。换句话说，让我们定义从 u 到 v 的最短路径为 a_1、a_2、...、a_k（其中 a_1 = u 和 a_k = v）。您必须找到 a_i 和 a_j 使得 i <= j 并且路径 a_i、a_(i + 1)、...、a_j 的边的权重之和尽可能大。你只需要找到那个总和。两个顶点 u 和 v 之间的最短路径是用最少数量的顶点连接它们的路径。在这个问题中，很明显 G 的任意一对顶点之间只有一条最短路径。a_(i + 1), ..., a_j 尽可能大。你只需要找到那个总和。两个顶点 u 和 v 之间的最短路径是用最少数量的顶点连接它们的路径。在这个问题中，很明显 G 的任意一对顶点之间只有一条最短路径。a_(i + 1), ..., a_j 尽可能大。你只需要找到那个总和。两个顶点 u 和 v 之间的最短路径是用最少数量的顶点连接它们的路径。在这个问题中，很明显 G 的任意一对顶点之间只有一条最短路径。