题目理解

我们有一个带权无向图，$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$。

代码实现

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
using namespace std;

typedef long long ll;
const ll INF = 1e18;

struct Edge {
    int to;
    ll len;
};

struct Node {
    int id;
    ll dist;
    bool operator<(const Node& other) const {
        return dist > other.dist;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, s, t, g, q;
    cin >> n >> m >> s >> t >> g >> q;

    vector<ll> h(n + 1), l(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> h[i] >> l[i];
    }

    vector<vector<Edge>> graph(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].push_back({v, w});
        graph[v].push_back({u, w});
    }
    vector<ll> deadline(n + 1, INF);
    for (int i = 1; i <= n; i++) {
        if (l[i] < h[i]) {
            deadline[i] = -1; 
        } else {
            if (q == 0) {
                deadline[i] = INF; 
            } else {
                deadline[i] = (l[i] - h[i]) / q;
            }
        }
    }

    vector<ll> dist(n + 1, INF);
    dist[s] = 0;
    priority_queue<Node> pq;
    pq.push({s, 0});

    while (!pq.empty()) {
        Node cur = pq.top();
        pq.pop();
        int u = cur.id;
        ll d = cur.dist;
        if (d != dist[u]) continue;

        for (const Edge& e : graph[u]) {
            int v = e.to;
            ll newTime = d + e.len;
            if (newTime > deadline[v]) continue;
            if (newTime < dist[v]) {
                dist[v] = newTime;
                pq.push({v, newTime});
            }
        }
    }

    if (dist[t] > g) {
        cout << "wtnap wa kotori no oyatsu desu!\n";
    } else {
        cout << dist[t] << "\n";
    }

    return 0;
}

样例验证

样例 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。