公路 (CSP-J 2023)

多层图DP松弛，最短路变形。

题意如下：给定一个有向图，边有开放时间，入口 $1$ 和出口 $n$ 每 $K$ 时间开放一次，每条边通过时间为 $1$ ，问从入口到出口的最短时间。根据条件，路线需要满足两个条件：

从入口到出口经过 $K$ 的整数倍条边
经过每条边时的起点时间大于等于这条边的开放时间 $a_i$

点数 $N \lt 10^4$ , 边数 $M \lt 2\cdot 10^4$ , 时间间隔 $K \lt 100$

我们看到 $K$ 很小，所以从 $K$ 入手。把时间模 $K$ ，这样我们就可以把时间转换为模 $K$ 的余数，图变成了 $K$ 层图。

我们定义 $\text{dist}[i][j]$ 为从入口经过 $\mod K$ 的 $j$ 条边，到达点 $i$ 的最早时间。然后答案就是 $\text{dist}[n][0]$ 。

然后用一个队列来管理活跃的点（开始为 $1$ ，起点），不断松弛 $\text{dist}[i][j]$ 数组就可以了。

具体就是，对于队列中的下一个点 $x$ ，我们遍历它的所有邻居 $y$ ，然后更新 $\text{dist}[y][\cdot]$ ，我们对 $i=0..K-1$ ：

如果 $\text{dist}[x][i]$ 不早于 $x-y$ 边的开放时间，则 $t=\text{dist}[x][i]$ ，如果早于，则t是大于等于开放时间的第一个 $\mod K$ 同余数。
如果 $t+1$ 小于 $\text{dist}[y][(t+1)\mod K]$ ，则更新 $\text{dist}[y][(t+1)\mod K]$ 为 $t+1$ ，并把 $y$ 加入队列。

细节见程序。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int n, m, k;
vector<pi> v[10005];        // edges with earliest time
int dist[10005][105];       // earliest time to reach a node, mod K
queue<int> q;
bool inq[10005];
 
int main() {
 
    scanf("%d %d %d", &n, &m, &k);
    for (int i = 0; i < m; i++) {
        int x, y, t;
        scanf("%d %d %d", &x, &y, &t);
        v[x].push_back({y, t});
    }
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < k; j++)
            dist[i][j] = 1e9;
    
    dist[1][0] = 0;
    q.push(1);
    inq[1] = true;
 
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        inq[x] = false;
        for (pi p : v[x]) {
            int y = p.first;
            int t0 = p.second;
            for (int i = 0; i < k; i++) {
                if (dist[x][i] >= 1e9) continue;
 
                // apply edge time limit
                int t = dist[x][i];
                if (t < t0)
                    t = (t0 - t + k-1) / k * k + t;
 
                // relax all neighbors
                int nt = (t + 1) % k;
                if (dist[y][nt] > t+1) {
                    dist[y][nt] = t+1;
                    if (!inq[y]) {
                        q.push(y);
                        inq[y] = true;
                    }
                }
            }
        }
    }
 
    printf("%d\n", dist[n][0] == 1e9 ? -1 : dist[n][0]);
 
    return 0;
}