最多使用一条收费道路的城市间最短路径求解方案问询

核心逻辑 #

我们只需要对比两种情况的最短耗时：全程走免费路的最快路线，以及恰好走一条收费路的最快路线，最后选耗时更短的那个就行。

具体实现步骤 #

1. 计算起点到所有节点的免费路最短耗时
   用Dijkstra算法（毕竟道路通行时间都是正数，适合这个算法），只走免费道路，算出从A到每个城市u的最快时间，记为dist_A[u]。

2. 计算终点到所有节点的免费路最短耗时
   同样用Dijkstra，把终点B当起点，只走免费道路，算出每个城市u到B的最快时间，记为dist_B[u]。（或者把图里的道路方向反过来，从B跑Dijkstra，结果是一样的）

3. 遍历所有收费路，计算单条收费路的最优组合耗时
   对每一条收费路（连接u和v，通行时间是w_toll），我们算两种可能的路径耗时：

   • 从A走免费路到u，走这条收费路到v，再走免费路到B：dist_A[u] + w_toll + dist_B[v]
   • 从A走免费路到v，走这条收费路到u，再走免费路到B：dist_A[v] + w_toll + dist_B[u]
     取这两个值里更小的那个，作为这条收费路能带来的最快耗时。然后把所有收费路的这个值收集起来，取最小的那个，记为min_toll_time。

4. 敲定最终最优路线
   把全程免费的耗时dist_A[B]和min_toll_time比一下：

   • 如果没有收费路，直接选全程免费的路线；
   • 如果min_toll_time比dist_A[B]小，就选对应那条收费路的组合路线；
   • 要是所有收费路组合都不如全程免费快，那还是选全程免费的路线。

额外说明 #

• 这个方法效率很高：两次Dijkstra的时间复杂度是O(m + n log n)，再加上遍历k条收费路的O(k)，整体复杂度很低，适合大规模的图；
• 不用考虑“用多条收费路”的情况，因为题目明确Bob最多只能用一条，直接排除这种可能。

内容的提问来源于stack exchange，提问作者picker