题目概述

本题是一个带时间窗口约束的最短路问题。JOI 帮成员需要在避开道路安检的条件下，从起点城市到达终点城市，求最少时间。

关键约束：经过道路 $i$ 时，必须满足出发时间 $x \leq C_i - L_i$，即要在安检开始前完成通行。

算法思路

核心思想：预处理 + 时间逆序处理

该解法通过巧妙的预处理和逆时间顺序处理查询，高效解决了大规模查询问题。

主要步骤

1. 基础最短路预处理

void dijk_many(int u, ll *d)

计算从每个城市出发，考虑时间周期约束的基础最短路。这里处理了跨天等待的情况：

• 如果当前时间可以直接通过：d[pos] + e[id].l
• 如果需要等待到第二天：d[pos] + S - dd + e[id].l

2. 两种特殊的最短路计算

dijk_minus：计算在某个时间阈值之前能够到达的最短路

if (sw - d[pos] <= e[id].c)  // 满足时间约束
    d[v] = min(d[v], d[pos] + e[id].l);

dijk_plus：计算从某个时间开始能够到达的最短路

if (sw + d[pos] <= e[id].c - e[id].l)  // 满足时间约束
    d[v] = min(d[v], d[pos] + e[id].l);

3. 关键数据结构：Pair

struct Pair {
    int u, eid;
    ll val;  // = e[eid].c - e[eid].l - d1[eid][u]
};

这里 val 表示从城市 $u$ 出发，能够使用边 $eid$ 的最晚出发时间。

4. 逆时间处理查询

sort(V.begin(), V.end(), [&](Qry x, Qry y) {
    return x.t > y.t;  // 按出发时间从晚到早排序
});

这样处理的好处是：对于较晚的出发时间，可用的道路较少；随着处理更早的查询，更多道路变得可用。

关键技巧

1. 时间窗口处理

通过 dijk_minus 和 dijk_plus 分别处理时间窗口的左右边界，将复杂的时间约束转化为标准的最短路问题。

2. 逆序处理

按出发时间从晚到早处理查询，使得道路的激活是单调的，避免重复计算。

3. 状态设计

d1[eid][u]：从城市 $u$ 出发，在边 $eid$ 过期前能够到达边起点的最短时间
d2[eid][v]：从边终点出发，在边过期时间内能够到达城市 $v$ 的最短时间

4. 跨天策略

通过 S - V[i].t + mdis[v][V[i].v] 处理等待到第二天的策略。

复杂度分析

• 预处理：$O(m \cdot n^2)$，其中 $n \leq 90, m \leq n(n-1)/2$
• 查询处理：$O(n^2 \cdot (m + Q))$
• 总复杂度：在数据范围内可行

算法亮点

1. 优雅的时间约束处理：将时间窗口转化为图上的可达性条件
2. 高效的查询处理：通过排序和单调性避免重复计算
3. 全面的策略考虑：同时处理当天出发和等待到第二天的策略
4. 模块化设计：不同的 Dijkstra 变种各司其职

总结

该解法通过巧妙的预处理和逆序处理，将带时间窗口约束的最短路问题转化为多个标准最短路问题的组合，既保证了正确性，又实现了高效处理大规模查询的目标。。