T3：

30%：

当T<= 10000的时候，可以设 vis[i][j] 代表到达第i个点时间为j是否合法。 这样是O(T*m)，可以拿到小数据。

另外的那30%：各种奇怪的骗分方法。选手自行考虑。

100%：

当T很大的时候，我们考虑 如果0 -> x -> n - 1路径时间为T，且 从x出发有一个时间为d的环，则 一定存在一个K满足 K + p*d = T（至少T满足条件），这样我们就能绕着环走p次就能构成一条时间为T的路径。

显然要求的路径一定经过 0，而且在合法情况下从0号点出发一定存在一条边，否则0号点和n - 1号就是不联通的。随便取一条边时间为d, 则能构成从0号点出发的一个时间为2d的环。这样原题就化为最短路问题了，dis[i][j] 代表到达i号点，时间为 j + p * 2d，最小的 j+p*2d，

最后判断dis[n -1][T % 2d] 是否小于等于T即可。

实际上就是在30%的基础上缩减状态。

时间复杂度为O(m*d)。