会员专享
请先
登录，登录后可使用今日免费解锁；
开通会员后可解锁完整内容。
解题思路
状态记成 (i,c)：人已经进入卡口 i，并且已经用掉 c 次反向。边权是进入下一个卡口的时刻，时刻只增不减，所以在这个状态图上做堆优化最短路。
出发时刻是 0。起点也要先进入自己的时间窗，进入时刻是 max(0,Ls)。若 0>Rs，起点就进不去，直接输出 −1。约束里 Rs≥0，这一支不会发生，代码仍按题意判断。
每条通道拆成两条有向边。从 u 到 v 耗时 w，不增加反向次数；从 v 到 u 耗时 z，反向次数加 1。设当前进入时刻是 x，沿某条边到达下一卡口的时刻是 y=x+ 耗时。若 y>R，这条边不能走。否则进入时刻是 max(y,L)。进入以后必须马上离开，所以下一跳的出发时刻就是这个进入时刻。
反向次数超过 K 的状态直接丢掉。堆按进入时刻从小到大弹出。第一次弹出终点时，三种反向次数里最早的那个已经确定，就是答案。所有状态都处理完仍没到终点，输出 −1。
