有个问题让我抓狂！
--这应该通过动态编程btw-来解决
我有80个城市，还有一个额外的出发城市。我被要求找到从一个城市到这80个城市的最短路径。但问题是旅行者既可以乘公共汽车也可以乘火车。
在输入中，将提供关于在两个特定城市之间是否存在火车道、在到特定城市之间如果存在公共汽车道、使用这些选项之一的旅行者的平均旅行时间以及在城市中公共汽车站和火车站之间的平均旅行时间(如果两者都具有的话(的信息。在前往特定城市的旅行中，我们最多可以更改一次交通方式。
我想我可以把这个问题抽象到一个层次，每个城市都是一个顶点，因为这个结构可能不是一个非循环图；我可能会使用像Bellman-Ford这样的算法，或者其他在O(V.E(时间内运行的算法。但两个城市之间可能有两条边，一条是公共汽车，另一条是火车。那我就不知道该怎么办了。因此，递归将取决于两个参数，指定的顶点和到达该城市的最大边数。但在这里，我想我有另一个关于火车巴士问题的参数，我不知道如何处理，因为正如我所说，我们在旅行中最多可能改变一次交通方式。
我担心的是，如果有两个城市我们可以在整个旅程中改变我们的交通选择，那么由于成本较低而改变第一个可能城市的交通选择可能不会导致最低的总成本，因为也许在第二个可能城市改变交通选择会比第一个城市降低更多的成本。
如有任何帮助，我们将不胜感激。提前感谢！
假设您只有总线选项，为了解决这个问题，您可以使用Dijkstra's algorithm，它通常用于查找从单个节点到另一个节点的路径，但可以很容易地进行修改，以查找到图中所有节点的最短路径。我们确实会把每个城市作为节点，把每条车道作为边缘，我们已经完成了：(
现在有趣的是，当你只能在火车和公共汽车之间切换一次时。让我们创建两个图，G_b和G_t，其中G_t只包含火车路径，G_b只包含公共汽车路径，权重是行程时间。下一步是用一个有向边将G_b中的所有节点连接到G_t中的相应节点。创建此图的另一个副本，但这次将G_t连接到G_b。
现在在这两张图上运行Dijkstra's algorithm。当你想知道哪个时间到一个特定的城市最短时，从这个城市的所有4次事件中取最小值
您可以通过检查我们是否更改了图中的图层来了解我们是否更改运输。
到目前为止，时间复杂度低于Bellman-Ford，因为我们只运行了两次Dijkstra的算法。O(E + V log V)
您可以选择将每个公交车站和每个火车站都设为节点，并在相邻的公交车站和相邻的火车站之间以及在同一城市的公交车站与火车站之间设置边缘，而不是将每个城市设为节点。然后你可以运行一些SSSP算法，也许是Dijkstra的，它运行得比Bellman-Ford快得多，适用于来自源城市的非循环图(前提是没有负边(。
为了确保您不会多次更改运输方式，您可以在每个状态中添加一个额外的布尔参数，该参数标记您以前是否更改过运输方式。