: 猫和老鼠)
2025年12月GESP真题及题解(C++八级): 猫和老鼠
题目描述
猫和老鼠所在的庄园可以视为一张由n nn个点和m mm条带权无向边构成的连通图。结点依次以1 , 2 , … , n 1,2,\ldots,n1,2,…,n编号，结点i ii（1 ≤ i ≤ n 1\le i\le n1≤i≤n）有价值为c i c_ici的奶酪。在m mm条带权无向边中，第i ii（1 ≤ i ≤ m 1\le i\le m1≤i≤m）条无向边连接结点u i u_iui与结点v i v_ivi，边权w i w_iwi表示猫和老鼠通过这条边所需的时间。
猫窝位于结点a aa，老鼠洞位于结点b bb。对于老鼠而言，结点u uu是安全的当且仅当：
- 老鼠能规划一条从结点u uu出发逃往老鼠洞的路径，使得对于路径上任意结点x xx（包括结点u uu与老鼠洞）都有：猫从猫窝出发到结点x xx的最短时间严格大于老鼠从结点u uu沿这条路径前往结点x xx所需的时间。
老鼠在拿取安全结点的奶酪时不存在被猫抓住的可能，但在拿取不是安全结点的奶酪时则不一定。为了确保万无一失，老鼠决定只拿取安全结点放置的奶酪。请你计算老鼠所能拿到的奶酪价值之和。
输入格式
第一行，两个正整数n , m n,mn,m，分别表示图的结点数与边数。
第二行，两个正整数a , b a,ba,b，分别表示猫窝的结点编号，以及老鼠洞的结点编号。
第三行，n nn个正整数c 1 , c 2 , … , c n c_1,c_2,\ldots,c_nc1,c2,…,cn，表示各个结点的奶酪价值。
接下来m mm行中的第i ii行（1 ≤ i ≤ m 1\le i\le m1≤i≤m）包含三个正整数u i , v i , w i u_i,v_i,w_iui,vi,wi，表示图中连接结点u i u_iui与结点v i v_ivi的边，边权为w i w_iwi。
输出格式
输出一行，一个整数，表示老鼠所能拿到的奶酪价值之和。
输入输出样例 1
输入 1
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
22输入输出样例 2
输入 2
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
3说明/提示
对于40 % 40\%40%的测试点，保证1 ≤ n ≤ 500 1\le n\le 5001≤n≤500，1 ≤ m ≤ 500 1\le m\le 5001≤m≤500。
对于所有测试点，保证1 ≤ n ≤ 10 5 1\le n\le 10^51≤n≤105，1 ≤ m ≤ 10 5 1\le m\le 10^51≤m≤105，1 ≤ a , b ≤ n 1\le a,b\le n1≤a,b≤n且a ≠ b a\neq ba=b，1 ≤ u i , v i ≤ n 1\le u_i,v_i\le n1≤ui,vi≤n，1 ≤ c i , w i ≤ 10 9 1\le c_i , w_i\le 10^91≤ci,wi≤109。
算法思路
- 计算猫的最短时间：从猫窝
a出发，使用 Dijkstra 算法计算到每个节点的最短时间dist_cat[]。 - 安全节点传播：从老鼠洞
b开始，逆向扩展安全节点。定义安全值H[u]表示从u到b的安全路径中，路径上所有节点x的dist_cat[x]减去老鼠从u到x的时间的最小值。初始时H[b] = dist_cat[b]。 - 扩展条件：对于当前安全节点
v和其邻居u，如果边权w(u,v) < H[v]，则u可能安全。计算u的候选安全值cand = min(dist_cat[u], H[v] - w(u,v))。若cand > 0且大于u当前的安全值，则更新H[u]并将u加入优先队列。 - 求和：所有
H[i] > 0的节点均为安全节点，将其奶酪价值相加得到答案。
代码实现
#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintMAXN=100010;constll INF=1e18;intn,m,a,b;ll c[MAXN];// 每个节点的奶酪价值vector<pair<int,ll>>adj[MAXN];// 邻接表存储图，pair为(邻居节点, 边权)ll dist_cat[MAXN];// 猫从窝点a到每个节点的最短时间ll H[MAXN];// H[u]表示节点u的安全值，即从u到b的安全路径中的最小时间差// 从起点start（猫窝a）运行Dijkstra算法，计算猫到每个节点的最短时间voiddijkstra(intstart){for(inti=1;i<=n;i++)dist_cat[i]=INF;dist_cat[start]=0;// 使用最小堆，按距离从小到大处理priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>>pq;pq.push({0,start});while(!pq.empty()){auto[d,u]=pq.top();pq.pop();if(d!=dist_cat[u])continue;// 跳过过时的记录for(auto[v,w]:adj[u]){if(dist_cat[v]>d+w){dist_cat[v]=d+w;pq.push({dist_cat[v],v});}}}}// 从老鼠洞b开始计算安全节点及其H值voidcompute_H(){for(inti=1;i<=n;i++)H[i]=-1;// -1表示尚未确定是否安全H[b]=dist_cat[b];// 老鼠洞b本身是安全的，其H值为猫到b的最短时间// 使用最大堆，按H值从大到小处理，以便优先扩展H值大的节点priority_queue<pair<ll,int>>pq;pq.push({H[b],b});while(!pq.empty()){auto[h_val,v]=pq.top();pq.pop();if(h_val!=H[v])continue;// 跳过过时的记录// 遍历v的所有邻居ufor(auto[u,w]:adj[v]){// 如果边权w严格小于v的当前H值，则考虑通过v使u安全if(w<h_val){// 计算u的候选H值：min(猫到u的最短时间, H[v] - w)ll cand=min(dist_cat[u],h_val-w);// 只有候选值大于0才表示u可能安全，并且大于当前记录的H值才更新if(cand>0&&cand>H[u]){H[u]=cand;pq.push({H[u],u});}}}}}intmain(){ios::sync_with_stdio(false);cin.tie(0);// 读入数据cin>>n>>m;cin>>a>>b;for(inti=1;i<=n;i++)cin>>c[i];for(inti=0;i<m;i++){intu,v;ll w;cin>>u>>v>>w;adj[u].push_back({v,w});adj[v].push_back({u,w});// 无向图，添加双向边}// 步骤1：计算猫从窝点a到所有节点的最短时间dijkstra(a);// 步骤2：从老鼠洞b开始计算所有安全节点compute_H();// 步骤3：累加所有安全节点的奶酪价值ll ans=0;for(inti=1;i<=n;i++){if(H[i]>0){// H[i] > 0 表示节点i是安全的ans+=c[i];}}cout<<ans<<endl;return0;}功能分析
时间复杂度
- Dijkstra 算法：
O((n+m) log n)。 - 安全节点扩展：每个节点和边可能被多次检查，但每个节点最多被更新一次（取最大 H 值），整体
O((n+m) log n)。 - 总复杂度：
O((n+m) log n)，可处理 n, m ≤10 5 10^5105的数据规模。
空间复杂度
- 使用邻接表存储图：
O(n+m)。 - 数组
dist_cat、H、c：O(n)。 - 优先队列：
O(n)。 - 总空间复杂度：
O(n+m)。
注意事项
- 使用
long long存储边权和距离，避免溢出。 - 安全节点必须满足
H[i] > 0，排除猫窝a（其dist_cat[a] = 0）。 - 扩展时使用最大堆优先处理
H值大的节点，以最大化安全区域的扩展。
各种学习资料，助力大家一站式学习和提升！！！
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}1、csp信奥赛高频考点知识详解及案例实践：
CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转
CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转
信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html
2、csp信奥赛冲刺一等奖有效刷题题解：
CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转
CSP信奥赛C++一等奖通关刷题题单及题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转
3、GESP C++考级真题题解：
GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转
GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转
GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html
4、CSP信奥赛C++竞赛拿奖视频课：
https://edu.csdn.net/course/detail/40437 点击跳转
· 文末祝福 ·
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}
