根据提供的标程思路，下面给出本题的详细题解。

---

题意简述

给定一张 $n$ 个节点、$m$ 条边的有向图（或无向图，按有向处理）。抢劫犯从节点 $1$ 出发，要逃往节点 $n$。节点 $k$ 是警察局。

• 对每条边 $i$，抢劫犯通过需要 $l_i$ 时间。
• 市民/警察通过边 $i$ 需要 $r_i$ 时间。
• 每个节点 $u$ 上都有市民，一旦抢劫犯到达 $u$，市民就会沿 $r$ 权最短路跑向警察局 $k$ 报警。
• 警察在接到报警后会立刻从 $k$ 出发，沿 $r$ 权最短路追捕。若警察在某节点（或边上）不晚于抢劫犯到达，则抢劫犯被抓。

问抢劫犯能否在 不被抓住 的前提下到达节点 $n$。

---

核心思路

1. 预处理市民报警时间

首先以 $k$ 为源点，边权为 $r$，执行经典 Dijkstra，得到每个节点 $u$ 到 $k$ 的最短时间 $d_u$。它表示：若有市民从 $u$ 出发跑向警察局，将在 $d_u$ 时间后报警；同时也表示警察从 $k$ 赶到 $u$ 的最短时间。

2. 抢劫犯的状态定义

令 $T_{\text{cur}}$ 为抢劫犯已经消耗的时间（从 $1$ 出发开始计），$T_{\text{warn}}$ 为 当前已知警察最早被通知的时刻。

定义状态 $(u,\,t)$，其中

$$t = T_{\text{cur}} - T_{\text{warn}}.$$

$t$ 的含义：若 $t<0$，表示距离警察接到通知还剩 $-t$ 时间；若 $t\ge 0$，表示警察已接到通知且已过去了 $t$ 时间。

初始状态：
抢劫犯在时刻 $0$ 位于 $1$，市民从 $1$ 报警需 $d_1$ 时间，因此 $T_{\text{cur}}=0,\ T_{\text{warn}}=d_1$，

$$t_1 = -d_1.$$

状态为 $(1,\,-d_1)$。

3. 状态转移

从状态 $(u,\,t)$ 出发，沿着边 $i$ 走到 $v$，边上的抢劫犯用时为 $l_i$。此时：

• 当前时间变为 $T_{\text{cur}}' = T_{\text{cur}} + l_i$；
• 节点 $v$ 上的市民会在 $T_{\text{cur}}' + d_v$ 时刻报警，故最早通知时刻更新为$$T_{\text{warn}}' = \min\!\big(T_{\text{warn}},\ T_{\text{cur}}' + d_v\big). $$

新状态的 $t'$ 为：

$$t' = T_{\text{cur}}' - T_{\text{warn}}' = \max\!\big(T_{\text{cur}}' - T_{\text{warn}},\ -d_v\big). $$

由于 $T_{\text{cur}}' - T_{\text{warn}} = t + l_i$，得到转移公式：

$$t' = \max(t + l_i,\ -d_v).$$

这个式子体现了两个下界：

• $t + l_i$：之前的最早通知时刻在走过该边后继续作用；
• $-d_v$：新市民可能更早报警，使通知时刻提前。

4. 修改的 Dijkstra 过程

我们维护一个优先队列，按 $t$ 值 从小到大 取出状态（即通知时刻相对当前时间差最小的状态优先处理）。算法流程如下：

1. 初始化优先队列，压入 $(1,\,-d_1)$。
2. 每次取出队首状态 $(u,\,t)$：
   • 若 $u$ 已被访问过，跳过；
   • 若 $d_u \le t$，表示警察到达 $u$ 的时刻 $T_{\text{warn}} + d_u \le T_{\text{cur}}$，即警察能在 $u$ 点抓住抢劫犯，该状态无效，跳过；
   • 否则标记 $u$ 已访问。若 $u = n$，则抢劫犯成功逃脱，答案为 YES。
3. 对 $u$ 的每条出边 $(u,v,l_i)$，计算 $t' = \max(t + l_i,\ -d_v)$，并将 $(v,\,t')$ 压入优先队列。
4. 若队列为空仍未访问到 $n$，输出 NO。

正确性说明：
$t$ 越小，意味着警察被通知的时刻相对当前时间越晚，对抢劫犯越有利。因此按 $t$ 从小到大扩展，本质是贪心地保留最大的逃生余量，可以类比最短路的贪心策略。上述剪枝条件 $d_u \le t$ 则相当于“若当前状态已无法避免被抓，则不再继续”。

5. 复杂度分析

• 第一次 Dijkstra：$O((n+m)\log n)$。
• 第二次修改 Dijkstra：每个节点最多入队一次，每条边最多松弛一次，优先队列操作 $O(\log(n+m))$。
• 总时间复杂度：$$O\big((n+m)\log(n+m)\big).$$

---

以下是基于题解思路的完整 C++ 实现。为了便于理解，已加入详细注释。

#include <bits/stdc++.h>
using namespace std;

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

struct Edge {
    int to;
    ll l, r; // 抢劫犯用时l，警察/市民用时r
};

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

    int n, m, k;
    cin >> n >> m >> k;

    vector<vector<Edge>> adj(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v;
        ll l, r;
        cin >> u >> v >> l >> r;
        adj[u].push_back({v, l, r});
        adj[v].push_back({u, l, r}); // 若无向图需此行，有向图请删除
    }

    // ---------- 第一次 Dijkstra：计算市民报警时间 d[u] ----------
    vector<ll> d(n + 1, INF);
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;
    d[k] = 0;
    pq.push({0, k});

    while (!pq.empty()) {
        auto [dist, u] = pq.top(); pq.pop();
        if (dist != d[u]) continue;
        for (auto &e : adj[u]) {
            int v = e.to;
            ll w = e.r;          // 市民沿 r 权跑
            if (d[v] > d[u] + w) {
                d[v] = d[u] + w;
                pq.push({d[v], v});
            }
        }
    }

    // ---------- 第二次修改 Dijkstra：抢劫犯逃生 ----------
    // 状态: (t, u)，t = T_cur - T_warn
    // 初始状态: T_cur=0, T_warn=d[1] -> t = -d[1]
    vector<bool> vis(n + 1, false);
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> states;
    ll t1 = -d[1];
    states.push({t1, 1});

    bool canEscape = false;
    while (!states.empty()) {
        auto [t, u] = states.top(); states.pop();
        if (vis[u]) continue;
        // 如果警察到达时刻 <= 抢劫犯到达时刻，则在此节点被抓，状态无效
        if (d[u] <= t) continue;

        vis[u] = true;
        if (u == n) {
            canEscape = true;
            break;
        }

        for (auto &e : adj[u]) {
            int v = e.to;
            ll l = e.l;
            // 转移: t' = max(t + l, -d[v])
            ll nt = max(t + l, -d[v]);
            if (!vis[v]) {
                states.push({nt, v});
            }
        }
    }

    cout << (canEscape ? "YES" : "NO") << "\n";
    return 0;
}

代码要点说明

• INF = 1e18，足够大但不会溢出 long long。
• 第一次 Dijkstra 得到 $d_u$，若某节点无法到达 $k$，则 $d_u = \text{INF}$，其相反数 -INF 在转移中会自动退化为只保留 $t + l_i$，逻辑正确。
• 第二次优先队列按 $t$ 从小到大弹出，等价于用最贪心的顺序扩展状态。
• 剪枝条件 d[u] <= t 精确实现了“警察能在 $u$ 点抓住抢劫犯则舍弃该状态”的判断。

时间复杂度

两次优先队列操作均为 $O((n+m)\log(n+m))$，空间 $O(n+m)$，符合标程要求。

总结

本题将警察通知时间与抢劫犯行动时间统一到一个差值状态 $t$ 中，通过一次预处理最短路和一次状态最短路，即可判断是否存在安全逃生路径。关键在于巧妙定义 $t = T_{\text{cur}} - T_{\text{warn}}$，并将市民报警的影响转化为转移式 $t' = \max(t + l_i, -d_v)$，使得问题可以使用优先队列高效求解。