题意
给定一个有向图 \(G\)，以及将所有边反向重连的无向图 \(T\)。
你最多可以在 \(T\) 上连续走 \(k\) 条边，走过每条边的代价都为 \(1\)，然后 必须 在 \(G\) 的对应点上走一条边以恢复体力。
若当前对应点没有出边，则停留在该点 \(1\) 代价。
求每个点到 \(n\) 的最小代价。
Sol
考虑 \(n\) 作为源点跑 \(\text{bfs}\)。
直接上 \(k\) 层图，发现休息不好弄。
集中注意力，假如我们钦定一条边作为最短路径，只要出边不止一条就会增加 \(2\) 的贡献。
但是这个东西假了，因为如果该点出边不存在比当前更差的出边，她还是会走到当前边，这样就变成了 \(1\) 的贡献。
所以我们固然可以考虑休息不用走一条边，只用考虑转移到自己就行了。
直接跑 \(\text{1 - 2 bfs}\) 即可。
但是都做到这里了，不难发现一些事情。
如果我们转移的出边是最后一条出边，根据 \(\text{bfs}\) 的定义，当前时间一定是最大的。
所以当前边是对方点的最后一条出边，直接转移即可，否则记录一下。
最后特判掉在当前停留的情况即可。
标签：一条,省选,text,YC307A,T1,bfs,出边,当前 From： https://www.cnblogs.com/cxqghzj/p/18262520