P14923 [GESP202512 八级] 猫和老鼠

发表于 更新于 分类于 ， ，

猫和老鼠所在的庄园可以视为一张由 n 个点和 m 条带权无向边构成的连通图。结点依次以 1, 2, …, n 编号，结点 i（1 ≤ i ≤ n）有价值为 ci 的奶酪。在 m 条带权无向边中，第 i（1 ≤ i ≤ m）条无向边连接结点 ui 与结点 vi，边权 wi 表示猫和老鼠通过这条边所需的时间。

猫窝位于结点 a，老鼠洞位于结点 b。对于老鼠而言，结点 u 是安全的当且仅当：

  • 老鼠能规划一条从结点 u 出发逃往老鼠洞的路径，使得对于路径上任意结点 x（包括结点 u 与老鼠洞）都有：猫从猫窝出发到结点 x 的最短时间严格大于老鼠从结点 u 沿这条路径前往结点 x 所需的时间。

老鼠在拿取安全结点的奶酪时不存在被猫抓住的可能，但在拿取不是安全结点的奶酪时则不一定。为了确保万无一失，老鼠决定只拿取安全结点放置的奶酪。请你计算老鼠所能拿到的奶酪价值之和。

输入格式

第一行，两个正整数 n, m，分别表示图的结点数与边数。

第二行，两个正整数 a, b，分别表示猫窝的结点编号，以及老鼠洞的结点编号。

第三行，n 个正整数 c1, c2, …, cn，表示各个结点的奶酪价值。

接下来 m 行中的第 i 行（1 ≤ i ≤ m）包含三个正整数 ui, vi, wi，表示图中连接结点 ui 与结点 vi 的边，边权为 wi。

输出格式

输出一行，一个整数，表示老鼠所能拿到的奶酪价值之和。

输入输出样例 #1

输入 #1

1
2
3
4
5
6
7
8
5 5
1 2
1 2 4 8 16
1 2 4
2 3 3
3 4 1
2 5 2
3 1 8

输出 #1

1
22

输入输出样例 #2

输入 #2

1
2
3
4
5
6
7
8
9
10
11
12
13
6 10
3 4
1 1 1 1 1 1
1 2 6
2 3 3
3 1 4
3 4 5
4 5 8
5 6 2
6 4 1
3 2 4
5 4 4
3 3 6

输出 #2

1
3

说明/提示

对于 40% 的测试点，保证 1 ≤ n ≤ 500，1 ≤ m ≤ 500。

对于所有测试点，保证 1 ≤ n ≤ 105，1 ≤ m ≤ 105，1 ≤ a, b ≤ n 且 a ≠ b，1 ≤ ui, vi ≤ n，1 ≤ wi ≤ 109。

注：GESP 原题缺失 ci 范围，可按 1 ≤ ci ≤ 109 计算。

题解

这是一个经典的图论问题，可以转化为最短路问题的变种。我们需要计算每个节点是否满足特定的“安全条件”。

核心思路解析

这个问题包含两个核心部分：

  1. 猫的行动：猫从 a 点出发，到任意点 x 的最短时间是固定的。我们可以用 Dijkstra 算法求出猫到所有点 x 的最短时间，记为 Dcat[x]。
  2. Jerry 的规划：Jerry 需要寻找一条从 u 到 b（老鼠洞）的路径，使得路径上任意一点 x，满足 Dcat[x] > TimeJerry(u → x)。

逆向思维推导

与其思考“Jerry 从 u 走到 b”，不如从老鼠洞 b 反向推导回到 u。

定义 S[u] 为：Jerry 在节点 u 时，相对于猫到达该点的时间，他拥有的最大“时间富余量”（Slack）。或者更准确地说，这是 Jerry 在 u 点可以“可以延迟多久出发”还能安全到达洞口的安全阈值。

根据题目定义，对于路径上的点 x（从 u 到 b），必须满足：

TimeJerry(u → x) < Dcat[x]

假设 Jerry 在 u 点耗费了 t 时间出发（虽然题目是从 0 开始，但为了递推，我们引入这个相对量），则到达 x 点的时间为 t + dist(u, x)。

安全条件变为：

t + dist(u, x) < Dcat[x] ⟹ t < Dcat[x] − dist(u, x)

这意味着，为了保证路径后续所有点都安全，Jerry 在 u 点的“最大容忍时间” S[u] 受限于路径上所有点的瓶颈。

递推公式（状态转移）：

我们从老鼠洞 b 开始倒推。

  • 基准情况：在老鼠洞 b，只要猫还没抓到他就是安全的。所以 S[b] = Dcat[b]。

  • 递推：假设我们已经知道节点 v 的安全余量 S[v]，现在有一条边 (u, v) 权重为 w（Jerry 实际上是 u → v）。

    Jerry 在 u 点的安全受到两个限制：

    1. u 点本身必须安全：时间必须小于 Dcat[u]。
    2. 通过 v 后续的路径必须安全：Jerry 从 u 到 v 走了 w 时间，到达 v 后，他剩余的“时间余额”变成了 S[v]。所以在 u 点，他相对于 v 的限制是 S[v] − w。

    综上，从 v 推导到 u 的状态转移方程为：

    S[u] = max (S[u], min (Dcat[u], S[v] − w))

我们需要求出每个点的最大 S[u]。这本质上是一个最大瓶颈路（Maximum Bottleneck Path）问题，可以使用类似 Dijkstra 的贪心算法（使用大顶堆）来解决。

判定标准：

如果计算出的 S[u] > 0，说明 Jerry 在 t = 0 时刻出发是满足严格小于猫的时间的，该节点安全。

算法步骤

  1. 计算猫的最短路：以 a 为起点运行标准 Dijkstra，求出所有点的 Dcat[i]。
  2. 计算安全余量：
    • 初始化所有点的 S[i] = −1。
    • 设 S[b] = Dcat[b]，将 (S[b], b) 加入大顶堆优先队列。
    • 运行“最大瓶颈路”算法：
      • 每次取出当前 S 值最大的点 v。
      • 遍历邻居 u（边权 w）：
      • 计算通过 v 能够给 u 带来的余量：limit = min (Dcat[u], S[v] − w)。
      • 如果 limit > S[u]，则更新 S[u] = limit，并将 u 入队。
  3. 统计结果：遍历所有节点 i，如果 S[i] > 0，则将 ci 加入总奶酪数。

C++ 示范代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

const long long INF = 1e18;

struct Edge {
    int to;
    long long w;
};

struct Node {
    int id;
    long long val;
    // 重载小于号用于优先队列
    bool operator>(const Node& other) const {
        return val > other.val; // 小顶堆用
    }
    bool operator<(const Node& other) const {
        return val < other.val; // 大顶堆用
    }
};

int n, m, a, b;
vector<long long> cheese;
vector<vector<Edge>> adj;

// 标准 Dijkstra 计算猫的最短路
vector<long long> get_cat_distances(int start_node) {
    vector<long long> dist(n + 1, INF);
    dist[start_node] = 0;
    priority_queue<Node, vector<Node>, greater<Node>> pq; // 小顶堆
    pq.push({start_node, 0});

    while (!pq.empty()) {
        Node current = pq.top();
        pq.pop();
        int u = current.id;
        long long d = current.val;

        if (d > dist[u]) continue;

        for (auto& edge : adj[u]) {
            if (dist[u] + edge.w < dist[edge.to]) {
                dist[edge.to] = dist[u] + edge.w;
                pq.push({edge.to, dist[edge.to]});
            }
        }
    }
    return dist;
}

// 类似 Dijkstra 的贪心算法计算 Jerry 的安全余量 (Slack)
vector<long long> get_safe_slack(int start_node, const vector<long long>& cat_dist) {
    vector<long long> slack(n + 1, -1);

    // 如果猫就在老鼠洞，余量直接为0（不安全，因为题目要求严格大于）
    // 但根据算法逻辑，初始 slack 设为 cat_dist[b] 即可
    slack[start_node] = cat_dist[start_node];

    priority_queue<Node> pq; // 大顶堆，优先处理余量大的路径
    pq.push({start_node, slack[start_node]});

    while (!pq.empty()) {
        Node current = pq.top();
        pq.pop();
        int u = current.id;     // 当前节点 (推导方向是从 洞 -> u -> ... -> 奶酪点)
        long long s = current.val;

        if (s < slack[u]) continue;

        for (auto& edge : adj[u]) {
            int v = edge.to; // v 是 u 的邻居 (推导方向 u -> v)
            long long w = edge.w;

            // 核心推导公式:
            // 我们从 u (靠近洞) 扩展到 v (远离洞)
            // v 的安全余量受限于：
            // 1. v 自身离猫的距离 (cat_dist[v])
            // 2. 从 u 传递过来的余量减去路程耗时 (slack[u] - w)
            long long next_slack = min(cat_dist[v], slack[u] - w);

            if (next_slack > slack[v]) {
                slack[v] = next_slack;
                pq.push({v, slack[v]});
            }
        }
    }
    return slack;
}

int main() {
    // 优化 I/O 速度
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    if (!(cin >> n >> m >> a >> b)) return 0;

    cheese.resize(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> cheese[i];
    }

    adj.resize(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v;
        long long w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    // 1. 计算猫到所有点的最短时间
    vector<long long> cat_dist = get_cat_distances(a);

    // 2. 计算 Jerry 从老鼠洞反向推导的安全余量
    vector<long long> slack = get_safe_slack(b, cat_dist);

    // 3. 统计结果
    long long total_cheese = 0;
    for (int i = 1; i <= n; ++i) {
        // 安全条件: 能够规划路线，且任意点猫到达时间 > Jerry到达时间
        // 这等价于我们在 t=0 时刻出发，拥有 > 0 的余量
        if (slack[i] > 0) {
            total_cheese += cheese[i];
        }
    }

    cout << total_cheese << endl;

    return 0;
}

样例说明

输入样例

Plaintext

1
2
3
4
5
6
7
5 5 1 5
10 20 30 40 50
1 2 10
2 3 10
3 4 10
4 5 10
2 5 35

样例解释

  • 图结构：一条链 1 − 2 − 3 − 4 − 5，加上一条边 2 − 5。
  • 位置：猫在 1，老鼠洞在 5。
  • 奶酪：c1 = 10, c2 = 20, c3 = 30, c4 = 40, c5 = 50。
  • 猫的到达时间 (Dcat)：
    • 1: 0 (起点)
    • 2: 10
    • 3: 20
    • 4: 30
    • 5: 40 (路径 1-2-3-4-5) 或 45 (路径 1-2-5)。最短是 40。
  • Jerry 的安全余量 (Slack) 计算（从 5 号点倒推）：
    • Node 5: Slack[5] = Dcat[5] = 40。
    • 推导 Node 4 (边权 10): min (Dcat[4], Slack[5] − 10) = min (30, 30) = 30。
    • 推导 Node 3 (边权 10): min (Dcat[3], Slack[4] − 10) = min (20, 20) = 20。
    • 推导 Node 2 (来自 3, 边权 10): min (Dcat[2], Slack[3] − 10) = min (10, 10) = 10。
    • 推导 Node 2 (来自 5, 边权 35): min (10, 40 − 35) = 5。最大值取 10。
    • 推导 Node 1 (边权 10): min (Dcat[1], Slack[2] − 10) = min (0, 0) = 0。
  • 判定：
    • Node 5: Slack = 40 > 0 (安全)
    • Node 4: Slack = 30 > 0 (安全)
    • Node 3: Slack = 20 > 0 (安全)
    • Node 2: Slack = 10 > 0 (安全)
    • Node 1: Slack = 0 (不安全，必须严格大于)
  • 结果：20 + 30 + 40 + 50 = 140。

输出

Plaintext

1
140