P1266 速度限制

基本思想:
看到这个题一开始的思路:正常以时间为边权跑dij,在v=0的时候把v设置成上一条路的速度,最后输出的时候记录路径
但是发现这个方法是错的...
因为我们发现一条v=0的路可以有很多速度,因为与之相连的边不一样,很有可能我们在之前用dij选择了最优解,但是到这一条边的时候由于速度问题,导致之前的最优解变劣了,所以这个方法不行
那么怎么办呢?
想到zhx说的一句话,如果状态多了一个,就躲开一维数组
所以我们可以设置数组:
dis[i][j]:出发点到点i,速度为j时(可以理解成j的前一个点到j的速度为j)的距离(时间)
vis[i][j]:同上

如果边(x,y)的速度为0,那么便有:
if(...)
	dis[y][old_v]=dis[x][old_v]+(x,y).s/old_v;
//old_v为上一条的限速(代码中为vs)

//(x,y)为连接x与y的边
- 如果边(x,y)有速度,那么便有:
if(...)
	dis[y][now_v]=dis[x][old_v]+(x,y).s/now_v;
//old_v为上一条的限速

//now_v为现在的限速

//(x,y)为连接x与y的边

即可...完美AC?

原文地址:https://www.cnblogs.com/yxr001002/p/14583347.html