问题分析

这是一个在时间轴上带周期性的最短路问题。 由于可以过夜，所以到达某个城市的时间可以跨天，我们需要找到最早到达目的地的时间。

关键点 只能向东走（从 $i$ 到 $i+1$），所以路线是单调的。

航班时间每天重复，跨天相当于加 $T$ 秒。

目标是最小化从出发到到达的总时间。

子任务分析

子任务 1 & 3 ($M_i = 1$) 每个城市只有一班飞机，那么从 $L$ 到 $R$ 的路径是唯一确定的（必须按顺序坐这些航班）。 我们可以直接模拟：

从 $L$ 出发，假设出发时间是 $t=0$（第一天 $0$ 时刻）。

对于 $i = L, L+1, \dots, R-1$：

找到从 $i$ 出发的航班时间 $A_i$ 和到达时间 $B_i$。

如果当前时间 $t \le A_i$，则当天可以赶上这班飞机，到达 $i+1$ 的时间是 $B_i$。

如果 $t > A_i$，则必须等到第二天，到达 $i+1$ 的时间是 $B_i + T$。

更新 $t$ 为到达时间。

总时间 = 到达 $R$ 的时间 - 出发时间（$0$）。

这样一次查询是 $O(R-L)$，最坏 $O(N)$，对于 $N \le 2000$ 和 $Q$ 较小的情况可行。

子任务 2 & 4 ($M_i \le 5$, $N \le 2000$) 每个城市有少量航班，我们可以用动态规划：

设 $dp[i][j]$ 表示到达城市 $i$ 且到达时刻是第 $j$ 个航班的到达时间（或某个离散化后的时间点）的最小出发时间？ 但这样状态太多，因为时间可以很大。

更好的方法： 设 $f(i, t)$ 表示在城市 $i$，当前时刻是 $t$（模 $T$ 意义下），到达这里所用的实际总时间（从出发开始算）。 但 $t$ 是模 $T$ 的，实际总时间需要记录天数。

实际上我们可以用 BFS 或 Dijkstra 的思想，但状态是 (城市, 时间模 $T$)，值是最小的实际到达时间（绝对时间）。 因为航班是周期性的，我们只关心在模 $T$ 下的到达时间，以及实际用了多少天。

实现方法（针对子任务 1,2,3,4）

对于小数据（$N \le 2000$），我们可以用 BFS 状态 (城市, 时间模 $T$) 来求解每个查询。 但 $Q$ 可能很大，需要一次性处理所有查询。

小数据做法（子任务 1,2,3,4） 预处理 $ans[l][r]$：

对每个 $1 \le l \le N$，用 BFS 求出从 $l$ 出发到所有 $r > l$ 的最小时间。

BFS 状态 (城市, 时间模 $T$)，用数组 $dist[i][r]$ 记录最小实际时间。

初始 $dist[l][0] = 0$，BFS 扩展：

对每个航班 $(A,B)$ 从 $i$：

对每个 $r$：

如果 $r \le A$:

新时间 = $dist[i][r] + (B - r)$

新模 = $B$

否则:

新时间 = $dist[i][r] + (T - r + B)$

新模 = $B$

如果新时间 < $dist[i+1][B]$，更新并加入队列。

对每个 $r$，$ans[l][i+1] = \min(ans[l][i+1], dist[i+1][r])$。

复杂度

$O(N^2 M T)$ 太大，但 $M$ 小且只对每个 $l$ 做一次，可接受。

代码实现（子任务 3: $M_i=1$）

cpp #include #include using namespace std;

int main() { int N, T; cin >> N >> T; vector A(N), B(N); for (int i = 1; i < N; i++) { int m; cin >> m; cin >> A[i] >> B[i]; }

int Q;
cin >> Q;
while (Q--) {
    int L, R;
    cin >> L >> R;
    long long t = 0; // 当前绝对时间（从出发开始）
    for (int i = L; i < R; i++) {
        if (t % T <= A[i]) {
            t += B[i] - (t % T);
        } else {
            t += T - (t % T) + B[i];
        }
    }
    cout << t << "\n";
}
return 0;}