题解：P9549 「PHOI-1」路虽远

hydk2012 · 2026-04-25 17:01:41 · 题解

闲话

路虽远，行则将至。

事虽难，作则必成。

这两句话或许可以用于概括我做这个题的心路历程。

思路

很好的一道分层图最短路，考察的细节也很多。

首先题意需要理解一下：给定一张图，然后对于每个点 u，你能通过边走向下一个点 v 条件有两种：

1. 此时灯是绿色的。
2. 此时灯是黄色的，你需要耗费一次闯黄灯机会才行，最多有 g 次机会。

对于这个规则大家都不陌生，但是有几个细节需要注意：

1. 如果此时是红灯，需要等到绿灯才能通行。
2. 如果此时是黄灯并且你没有闯黄灯的机会了，你需要等到绿灯才能通行。

如果说这几个细节你没有考虑到，那么你会获得一个看上去基本全对的评测记录，然后就是找不到自己哪里错了（~像我一样~）。

接着还有一个规则就是限速规则，即在所有的边中，有 k 条边是有限速的。对于每一条边，没有限速的行驶时间是 \le 有限速的情况的。所以这个规则相当于有 m-k 条边没有限速。

很显然是一个分层图最短路的形式了。

我们定义 dis_{i,j,k} 为走到 i 点时走了 j 个不限速道路，且闯了 k 个黄灯的情况。

那么我们先需要求出一个 r 表示对于当前这个红绿灯，目前是在这个红绿灯的亮灯周期内的第多少秒。通过这个 r。我们可以得出这个红绿灯当前的颜色，便于我们后面处理。

接下来分两种情况：这条路限速和不限速。

在每种情况里面对于每一种颜色的灯进行判断并且分别进行松弛操作。

• 如果当前是红灯，则要加上等到绿灯的时间，然后加上通过时间进行松弛操作。
• 如果当前是绿灯，则直接加上通过时间松弛操作。
• 如果当前是黄灯，则分情况。一种是像红灯一样，加上等到绿灯的时间，然后加上通过时间进行松弛操作。另一种是如果还有闯黄灯机会，耗费一次机会，省去等黄灯时间。

然后对于里面的通过时间，就是我们在外面分的限速和不限速时间。

接着跑 Dijkstra 即可。

代码就不放了（~太史山了~），如果理解了按分层图最短路的方式写起来很快的，注意一些细节即可。