Back to Leetcode

Readme

BFS/1928.Minimum-Cost-to-Reach-Destination-in-Time/Readme.md

latest1.6 KB
Original Source

1928.Minimum-Cost-to-Reach-Destination-in-Time

求最短路径的题目,首选考虑常规的BFS和Dijsktra。因为本题有两个维度,时间和费用,所以Dijsktra不是很容易想。我们就考虑常规的BFS。

我们会注意到,对于任意一个中转城市C,假设有两种方案:时间10和花费20,时间20和花费10,这两种方案并没有明显的优劣之分,它们都有可能是到达终点的必经之路。前者虽然花费多,但用时少;后者虽然花费少,但用时多,可能会最终导致无法按时到达终点。所以我们在BFS的时候,不能将认为某个城市访问过了就不用再访问了,而是要把时间也当做一个状态。在不同时间到达不同的城市,都有可能影响最终结果。我们用dp[city][time]记录在time时刻到达城市city的最小花费。初始状态就是dp[0][0]=passingFees[0],将{city=0,time=0}加入队列之中,然后根据edge的几何关系进行拓展到下邻接的{nextCity, nextTime}。

BFS的过程中,如果发现dp[city][time]已经赋值过了,但是搜索到了该状态的更小花费,那么我们就需要再将{city,time}放入队列中重新拓展搜索。

最终BFS的结果是将所有可能达到的dp[city][time]都赋值了一遍。我们的答案是min{dp[n-1][t]}, for t=0,1,2,..maxTime

此外,有一个加速的技巧就是,我们到达{city,time}的状态时,可以看一下历史上曾经记录过的、最早访问该city的时刻earliestTime。如果dp[city][earliestTime] < dp[city][time],那么{city,time}这个状态就没有价值,不必再放入队列中。