题目回顾

我们有一个 $n$ 个节点、$m$ 条边的无向连通图。每条边有两种通行方式：

• 坐公交车：耗时 $l_{i1}$ 分钟
• 步行：耗时 $l_{i2}$ 分钟，且 $l_{i2} > l_{i1}$

要求在 $[t_1, t_2]$ 时间段内不能乘坐公交车（只能步行或停留），必须在 $t_0$ 时刻之前到达节点 $n$。问：从节点 $1$ 出发的最晚时间是多少？

---

核心思路

我们反过来思考：从终点 $n$ 出发，倒着推导每个节点最晚可以什么时候出发，才能准时到达 $n$。

设 $dist[u]$ 表示从节点 $u$ 出发，能够到达节点 $n$ 且不晚于 $t_0$ 的最晚出发时间。

显然：

• $dist[n] = t_0$（在终点，最晚出发时间就是 $t_0$ 本身）
• 对于其他节点，我们通过逆向的“松弛”操作来更新。

---

逆向松弛规则

考虑从节点 $v$ 反向走到节点 $u$（原图中 $u \to v$ 有一条边）。
已知从 $v$ 出发的最晚时间是 $d = dist[v]$，我们要计算从 $u$ 出发的最晚时间 $d_1$。

情况分析

如果从 $u$ 在时间 $d_1$ 出发，经过这条边到达 $v$ 的时间是：

• 坐公交：$d_1 + l_1$
• 步行：$d_1 + l_2$

到达 $v$ 的时间必须 $\le d$（因为 $d$ 是 $v$ 的最晚出发时间，且出发后不能再等，否则会晚于 $d$ 到达 $v$ 的出发时刻）。

所以：

• 若坐公交：$d_1 + l_1 \le d \implies d_1 \le d - l_1$
• 若步行：$d_1 + l_2 \le d \implies d_1 \le d - l_2$

我们想要 最大 的 $d_1$，即 $d_1 = \max($坐公交可行的最晚时间, 步行可行的最晚时间$)$。

---

公交可行条件

坐公交时，必须避免在 $[t_1, t_2]$ 期间乘车。
乘车时间段是 $[d_1, d_1 + l_1]$（因为 $d_1$ 出发，$l_1$ 分钟后到达）。

这个区间不能与 $[t_1, t_2]$ 有重叠（不能部分重叠，也不能完全包含）。

等价条件：
要么 $d_1 + l_1 \le t_1$（在通话开始前结束）
要么 $d_1 \ge t_2$（在通话结束后开始）

---

计算 $d_1$

从 $d_1 \le d - l_1$ 且公交可行，我们得到：

情况 A：若 $d - l_1 \le t_1$，则取 $d_1 = d - l_1$（因为此时 $d_1 + l_1 \le t_1$，自动满足）。

情况 B：若 $d - l_1 \ge t_2$，则取 $d_1 = d - l_1$（因为此时 $d_1 \ge t_2$，自动满足）。

情况 C：若 $t_1 < d - l_1 < t_2$，则不能直接取 $d - l_1$，因为乘车会覆盖通话区间。
此时最晚可行是：在 $t_2$ 时刻开始乘车，即 $d_1 = t_2$，但这会导致 $d_1 + l_1 = t_2 + l_1 > d$（因为 $d - l_1 < t_2$ 意味着 $t_2 + l_1 > d$），不满足到达时间 $\le d$。
所以这种情况不能坐公交，只能考虑步行。

---

总结公式

设 $d_{\text{bus}} = d - l_1$。

如果 $d_{\text{bus}} \le t_1$ 或 $d_{\text{bus}} \ge t_2$，则公交可行，$d_1^{\text{bus}} = d_{\text{bus}}$。

否则公交不可行，$d_1^{\text{bus}} = -\infty$。

步行总是可行（因为通话期间可以步行），但步行耗时更长：
$d_1^{\text{walk}} = d - l_2$。

最终：

$$d_1 = \max(d_1^{\text{bus}}, d_1^{\text{walk}})$$

---

特殊情况

如果 $d - l_2$ 落在通话区间内，没问题，因为步行允许。
但注意：如果公交不可行，我们可能需要在起点等一会儿再出发，使得乘车区间避开通话。
等多久？等到 $t_2$ 再出发，但这样到达 $v$ 的时间是 $t_2 + l_1$，必须 $\le d$。
所以如果 $t_2 + l_1 \le d$，那么 $d_1 = t_2$ 也是可行的。

这在代码中体现为：

if(d1 == d - l2) d1 = max(d1, t1 - l1);

实际上这里更准确的理解是：如果选择了步行方案，我们还可以考虑在起点等到 $t_1$ 再坐公交？等一下，原代码这里有些简略，我们分析官方逻辑。

---

官方代码逻辑解读

int d1 = (d - l1 >= t2 || d <= t1) ? d - l1 : d - l2;
if(d1 == d - l2) d1 = max(d1, t1 - l1);

第一行：

• 如果 $d - l_1 \ge t_2$ 或 $d \le t_1$，则公交可行，取 $d_1 = d - l_1$。
• 否则公交不可行，取步行 $d_1 = d - l_2$。

第二行：如果选了步行（即 $d_1 = d - l_2$），再尝试一个优化：
在 $t_1$ 时刻出发坐公交（到达 $v$ 的时间是 $t_1 + l_1$，必须 $\le d$，即 $t_1 + l_1 \le d$），那么 $d_1 = t_1$ 也可以。
但注意：这里代码写的是 $t_1 - l_1$？显然不对，应该是 $t_1$。
实际上原代码有误？我们仔细看：
$d_1 = \max(d - l_2, t_1 - l_1)$ 这个 $-l_1$ 很奇怪，可能是想表达：等到 $t_1$ 再出发，但 $t_1$ 是绝对时间，$d_1$ 也是绝对出发时间，不应该减 $l_1$。

更合理的解释：这里 $t_1 - l_1$ 可能是笔误，应该是 $t_1$。但为了尊重原代码，我们保留其形式。实际上正确逻辑是：

• 如果步行，也可以选择等到 $t_1$ 再出发坐公交（如果 $t_1 + l_1 \le d$），那么 $d_1 = t_1$。
• 同时也可以等到 $t_2$ 再出发坐公交（如果 $t_2 + l_1 \le d$），取最大值。

所以官方代码简化了，只考虑了 $t_1$ 的情况。

---

算法流程

1. 初始化 $dist[n-1] = t_0$，其余 $dist = -\infty$。
2. 使用最大堆（或 set 按值降序）进行类 Dijkstra 的逆向松弛。
3. 对于当前节点 $u$ 的最晚时间 $d$，遍历所有邻边 $(u, v, l_1, l_2)$：
   • 计算 $d_1$ 如上。
   • 若 $d_1 > dist[v]$，更新 $dist[v]$ 并加入堆。
4. 最终 $dist[0]$ 即为从节点 $1$ 出发的最晚时间。若为负数，输出 $-1$。

---

时间复杂度

每个节点和每条边最多被松弛一次，使用优先队列（或 set）复杂度 $O((n + m) \log n)$。
总 $n, m$ 和不超过 $10^5$，可接受。

---

示例验证

以第一个样例为例：

• $n=5, m=5, t_0=100, t_1=20, t_2=80$
• 边：$(1,5,30,100)$ 等

逆向从节点 $5$ 开始：

• $dist[5]=100$
• 边 $(1,5,30,100)$：$d=100$，$d-l_1=70$，在 $(20,80)$ 内，公交不可行，取步行 $100-100=0$，再尝试 $t_1 - l_1 = 20-30=-10$，取 $0$。所以 $dist[1]=0$。输出 $0$，符合样例。

---

总结

本题的关键是逆向思维 + 分段判断公交可行性，在 Dijkstra 框架下处理带时间窗口限制的最晚出发时间问题。