题解 P1266 【速度限制】

2018-10-21 16:15:00


题解好少qwq


这题显然是最短路,但是加入了速度这个量。所以可以当做二维最短路。

设 $dis[i][j]$ 表示到 $i$ 这个点,速度为 $j$ 的最短时间。

然后直接跑最短路即可。

注意到图中没有负权边,SPFA大概不会被卡。

然后还要输出路径,直接记录前置状态即可。最后递归输出。

细节见代码