题解：洛谷 P14923 [GESP202512 八级] 猫和老鼠

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P14923 [GESP202512 八级] 猫和老鼠 - 洛谷【题目描述】猫和老鼠所在的庄园可以视为一张由n nn个点和m mm条带权无向边构成的连通图。结点依次以1 , 2 , … , n 1,2,\ldots,n1,2,…,n编号结点i ii1 ≤ i ≤ n 1\le i\le n1≤i≤n有价值为c i c_ici​的奶酪。在m mm条带权无向边中第i ii1 ≤ 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​。【输出】输出一行一个整数表示老鼠所能拿到的奶酪价值之和。【输入样例】5 5 1 2 1 2 4 8 16 1 2 4 2 3 3 3 4 1 2 5 2 3 1 8【输出样例】22【算法标签】#普及# #Dijkstra#【代码详解】#includebits/stdc.husingnamespacestd;#defineintlonglongconstintN100005;intn,m,a,b;// n: 节点数, m: 边数, a: 节点A, b: 源点intc[N];// 每个节点的权值intans;// 最终答案intdist[N];// 从源点b到各节点的最短距离structNode{intv,w;// v: 目标节点, w: 距离/边权};vectorNodeg[N];// 邻接表存储图priority_queueNode,vectorNodepq;// 优先队列用于Dijkstrabooloperator(Node x,Node y)// 重载运算符使优先队列成为小顶堆{returnx.wy.w;// 注意priority_queue默认是大顶堆这里用实现小顶堆}boolst[N];// Dijkstra访问标记标记节点是否已确定最短路径// Dijkstra算法计算从节点b到所有节点的最短距离voiddijkstra(){memset(dist,0x3f,sizeof(dist));// 初始化所有距离为无穷大pq.push({b,0});// 从b点开始距离为0dist[b]0;// 源点b到自己的距离为0while(!pq.empty()){intupq.top().v;// 当前节点intwpq.top().w;// 当前距离pq.pop();if(st[u])// 如果已确定最短路径跳过{continue;}st[u]true;// 标记为已确定dist[u]w;// 记录最短距离这里w已经是dist[u]但赋值确保一致性// 遍历当前节点的所有邻接边for(inti0;ig[u].size();i){intvg[u][i].v;// 邻接节点intweightg[u][i].w;// 边权// 松弛操作如果通过u到达v更短则更新if(dist[v]dist[u]weight){dist[v]dist[u]weight;// 更新最短距离pq.push({v,dist[v]});// 入队}}}}signedmain(){cinnmab;// 输入节点数、边数、两个特殊节点// 输入每个节点的权值for(inti1;in;i){cinc[i];}// 输入图的边while(m--){intu,v,w;cinuvw;g[u].push_back({v,w});// 无向图g[v].push_back({u,w});// 无向图}dijkstra();// 运行Dijkstra算法计算从b到所有节点的最短距离// 统计所有到b的距离小于到a距离的节点的权值和for(inti1;in;i){if(dist[i]dist[a])// 如果节点i到b的距离小于a到b的距离{ansc[i];// 累加节点i的权值}}coutansendl;// 输出结果return0;// 程序正常结束}【运行结果】5 5 1 2 1 2 4 8 16 1 2 4 2 3 3 3 4 1 2 5 2 3 1 8 22