Readme

1976.Number-of-Ways-to-Arrive-at-Destination

如果是求起点到终点的最短时间，那么可以采用标准的Dijsktra算法。但是本题更进一步，需要求最短距离的方案数，有什么变化呢。

比较直观的想法就是倒推。假设从起点到终点的最短时间是T，并且终点的邻接城市是Ai（距离是ti），那么意味着我们需要在T-ti的时间到达Ai。同时我们注意到Dijsktra算法可以求得起点到任意位置的最短时间T[Ai]，那么我们就可以发现：如果T > T[Ai] + ti，这是不可能的，否则我们就找到了一条里终点更短的路径. 如果T < T[Ai] + t[i]，那么Ai也不会是最优路径上的一点，因为起点->Ai->终点的耗时会更长。所以我们知道最优路径的倒数第二站，应该是那些满足T = T[Ai]+ti的位置。所以我们就可以递归得到

count(Destination) = sum { count(Ai) } , for T[Ai] + ti = T[Destination]

由此我们可以递归下去。边界条件是count(Start) = 0.