Readme

2045.Second-Minimum-Time-to-Reach-Destination

这道题很多人看到最短路径就下意识地用Dijkstra算法。事实上这是不必要的，否则还会造成TLE。

很多最短路径问题需要使用Dijkstra算法的原因，在于各个边的权重并不一致。传统的BFS算法里，弹出队首元素cur -> 扩展至若干相邻元素nxt = cur + edge(cur->nxt) -> 将nxt放入队尾，这个流程会因为edge长度的不同，造成队列里面的节点所对应的路径并不保证递增。因此当我们从队列里第一次弹出终点时，并不能保证就是最短距离。于是Dijkstra就利用了贪心的思想，实时把当前最优（某个节点）的解弹出，直到我们遇到终点。

在本题中，虽然有了红绿灯的干扰，但是我们仔细想一想，无论什么情况下，后加入的节点时间一定会比先加入的节点时间晚。不可能出现这种情况：A先弹出可到达C，B后弹出可到达D，结果D比C的到达时间反而早。这是因为即使A被红灯耽搁了出发，那么B必然不会赶在那个红灯前出发。无论如何D不会早C。

基于以上分析，传统的BFS就可以解这道题了。本题tricky的地方在于求到达终点的第二最短路径（时间）。传统的BFS求最短路径，每个节点我们只需要访问一次，任何路径如果访问了二次相同的节点必然不会是最短距离。但本题中，我们BFS需要遍历每个节点两次，即得到它的最早到达和次早到达时间。但也仅此而已。因为在从起点到终点的第二最短路径所经过的所有节点里，肯定不会有某个节点被走了3次或以上。这个可以反证。假设从起点到终点的第二最短路径经过了A->...->B1->...->B2->...->B3->...->C，那么我们只要把多绕的圈子去掉，必然有两条更短的路径A->...->B1->...->B2->...-->C和A->...->B1->...->C。