题目理解

我们有一个带权无向图，$n$ 个点，$m$ 条边。
起点 $s$，终点 $t$，要求在 $g$ 秒内到达。

特殊条件：

• 每个点 $i$ 初始积雪深度 $h_i$，雪深限制 $l_i$。
• 每秒钟雪增加 $q$ mm。
• 到达某个点的时间为 $T$ 秒时，该点雪深为 $h_i + q \times T$。
• 如果到达时雪深 $> l_i$，则无法继续前进（被困住）。

目标：求从 $s$ 到 $t$ 的最短时间（秒），如果超过 $g$ 或无法到达，输出固定字符串。

关键点分析

1. 雪深限制条件

在点 $i$ 到达时间 $T$ 必须满足： [ h_i + q \times T \le l_i ] 即： [ T \le \frac{l_i - h_i}{q} \quad (\text{如果 } q > 0) ] 如果 $q = 0$，则条件简化为 $h_i \le l_i$（初始就满足才能进入）。

如果 $q > 0$，那么每个点 $i$ 有一个最晚到达时间： [ \text{deadline}[i] = \left\lfloor \frac{l_i - h_i}{q} \right\rfloor ] 如果 $l_i - h_i < 0$，则 $\text{deadline}[i] = -1$，表示永远不能到达（一开始雪就超限）。

2. 问题转化

我们要求最短时间 $d[t]$，同时保证在任意点 $i$ 的到达时间 $d[i] \le \text{deadline}[i]$。

这相当于在普通 Dijkstra 最短路的基础上，增加了一个时间上限约束。

3. 算法思路

用 Dijkstra 算法求最短时间，但松弛边时要检查：

• 到达下一个点 $v$ 的时间 $newTime = d[u] + w$ 是否超过该点的 deadline。
• 如果超过，则不能走这条边。

注意：即使 $d[u] + w$ 不超过 deadline[$v$]，我们也要正常更新，因为可能更早到达 $v$ 对后续更有利。

4. 特殊情况处理

• $q = 0$：此时雪不增加，只需初始 $h_i \le l_i$ 的点才能访问。如果初始 $h_i > l_i$，则 deadline[$i$] = -1。
• $q > 0$：按上面公式计算 deadline。
• 如果 $l_i - h_i \ge 0$ 且 $q = 0$，则 deadline[$i$] = INF（无限大）。
• 如果 $l_i - h_i < 0$，deadline[$i$] = -1（不可达）。
• 如果 $q > 0$ 且 $l_i - h_i \ge 0$，deadline[$i$] = $(l_i - h_i) / q$（下取整）。

5. 复杂度

使用优先队列 Dijkstra，复杂度 $O((n+m)\log n)$，可以处理 $n \le 10^5, m \le 5\times 10^5$。

样例验证

样例 1
$n=2, m=1, s=1, t=2, g=10, q=1$
$h=[0,1,3], l=[0,10,10]$
边：1-2 长度 6

计算 deadline：
点1: $(10-1)/1 = 9$
点2: $(10-3)/1 = 7$

从 1 到 2 时间 6 ≤ 7，可以到达。输出 6。

样例 3
点3的 $h_3=10, l_3=10$，$q=1$，deadline[3] = 0，意味着必须在 0 秒内到达点3，这不可能，所以某些路径被阻断，导致无法到达终点。

总结

这道题本质是带时间约束的最短路，约束是每个点有一个最晚到达时间。
用 Dijkstra 求解时，在松弛边时检查时间约束即可。
注意 $q=0$ 和 $q>0$ 时 deadline 的计算方式不同，以及数据范围要用 long long。