这道题目本身不算难，只是有一点点小的最短路算法的改动
我们首先从分层图的角度考虑这个问题，每一层代表一秒钟
在第一层，最开始只有\(1\)在集合中，然后我们扫描第一层中\(1\)的所有出边，将终点全部加入到集合中
在第二层，我们扫描集合中所有点在第二层中的出边，把不在集合中的终点全部加入集合
每一层我们都这么做，最早的一层加入\(n\)的时候就是答案
但是上面的时间复杂度非常大，所以我们考虑优化，然而却没有很好的优化的方法，所以我们转换考虑对象，不从每一层去考虑，而是考虑每一个点什么时候被最早加入
我们考虑一个点\(u\)在\(d_u\)时刻被加入集合，那么他的贡献就是对其所有的时间大于\(d_u\)的出边的终点做出来的，所以我们有如下算法：
对每一个边集，存储其所有的时间；对每一个点，他的每一条边既包含终点也包含这条边所在的边集
于是我们在dij更新的时候，假设当前是\(u\)点，边为\((v,id)\)，其中\(id\)是这条边所属的边集，我们查找\(id\)大于\(d_u\)时刻的最早的时刻，用这个时刻更新\(d_v\)就好了
标签：终点,Travel,边集,出边,Time,集合,我们,id From： https://www.cnblogs.com/dingxingdi/p/18080392