图上权重变化的最短路径
Shortest path on graph with changing weights
我正在尝试解决本地编程竞赛问题。问题基本上是关于在加权图中找到最短路径。我对这些类型的问题还很陌生，我想我可以使用 Dijkstra 的算法。但是，有一个小问题 - 某些值会有所不同，具体取决于当前路径的情况。
问题
有两种类型的权重：正常权重和有条件的权重（我们称它们为 K）。条件是这样的：一旦你穿过权重为 K 的边，所有其他类型 K 的权重的值为 0。这带来了更多的问题，因为明显的最短路径可以被权重类型为 K 的边的组合击败.
例子
下面是这类问题。如果没有权重会改变它们的值，我们可以使用 Dijkstra 轻松找到最短路径。然而，当权值 K 改变它们的值时，我们可以找到一条更短的路径，因为边 C-D 的权值在经过边 A-C 后为 0。
问题
如何找到最短路径？
我可以在这里使用 Dijkstra 算法还是使用 A* 或 BFS 等其他算法更好？
一共有多少个K？
我只有一个，Dijkstra不错。
我要补充说 BFS 不能很好地处理重量。
温馨提示：Dijkstra求的是一个顶点到所有顶点的最短路径。
运行 Dijkstra 两次并为每个 运行 定义不同的 wight 函数。首先，K 值的怀特函数是无限的。 K 值的第二个权重函数为 0。
比较 运行1 和 运行2+K 的结果。
这是真的，因为如果最短路径没有 K，那么 运行 会找到它。否则它与 K 一起，第二个 运行 会找到它。无论哪种方式，算法都会找到它。
我正在尝试解决本地编程竞赛问题。问题基本上是关于在加权图中找到最短路径。我对这些类型的问题还很陌生，我想我可以使用 Dijkstra 的算法。但是，有一个小问题 - 某些值会有所不同，具体取决于当前路径的情况。
问题
有两种类型的权重：正常权重和有条件的权重（我们称它们为 K）。条件是这样的：一旦你穿过权重为 K 的边，所有其他类型 K 的权重的值为 0。这带来了更多的问题，因为明显的最短路径可以被权重类型为 K 的边的组合击败.
例子
下面是这类问题。如果没有权重会改变它们的值，我们可以使用 Dijkstra 轻松找到最短路径。然而，当权值 K 改变它们的值时，我们可以找到一条更短的路径，因为边 C-D 的权值在经过边 A-C 后为 0。
问题
如何找到最短路径？
我可以在这里使用 Dijkstra 算法还是使用 A* 或 BFS 等其他算法更好？
一共有多少个K？
我只有一个，Dijkstra不错。 我要补充说 BFS 不能很好地处理重量。
温馨提示：Dijkstra求的是一个顶点到所有顶点的最短路径。
运行 Dijkstra 两次并为每个 运行 定义不同的 wight 函数。首先，K 值的怀特函数是无限的。 K 值的第二个权重函数为 0。
比较 运行1 和 运行2+K 的结果。
这是真的，因为如果最短路径没有 K，那么 运行 会找到它。否则它与 K 一起，第二个 运行 会找到它。无论哪种方式，算法都会找到它。