Readme

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}这个状态就没有价值，不必再放入队列中。