P1266速度限制
不难看出，这道题除了“有些道路没有速度限制”，就是一个裸的最短路。
我们可以用分层图的思想，将速度 \(v\) 看做单独的一维，另 \(dis[i][j]\) 表示从起点到点 \(i\) ，并且当前速度为 \(j\) 时的最短路。
于是 \(Dij\) 的状态转移方程就是：
当前边有速度限制时： \(dis[ver[i]][v(fir.f,ver[i])]=dis[fir.f][fir.v]+len(fir.f,ver[i])/v(fir.f,ver[i])\) ;
当前边没有速度限制时：\(dis[ver[i]][fir.v]=dis[fir.f][fir.v]+len(fir.f,ver[i])/fir.v\)
图论基础
发布时间 2023-04-18 11:55:28作者: andy_lz