企业官网建设流程全解析

做家具城网站的意义,社群营销成功案例,怎么给网站做网页,极简wordpress模板2025年12月GESP真题及题解(C八级): 猫和老鼠 题目描述 猫和老鼠所在的庄园可以视为一张由 nnn 个点和 mmm 条带权无向边构成的连通图。结点依次以 1,2,…,n1,2,\ldots,n1,2,…,n 编号#xff0c;结点 iii#xff08;1≤i≤n1\le i\le n1≤i≤n#xff09;有价值为 cic_ici​…2025年12月GESP真题及题解(C八级): 猫和老鼠题目描述猫和老鼠所在的庄园可以视为一张由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​。输出格式输出一行一个整数表示老鼠所能拿到的奶酪价值之和。输入输出样例 1输入 15 5 1 2 1 2 4 8 16 1 2 4 2 3 3 3 4 1 2 5 2 3 1 8输出 122输入输出样例 2输入 26 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输出 23说明/提示对于40 % 40\%40%的测试点保证1 ≤ n ≤ 500 1\le n\le 5001≤n≤5001 ≤ m ≤ 500 1\le m\le 5001≤m≤500。对于所有测试点保证1 ≤ n ≤ 10 5 1\le n\le 10^51≤n≤1051 ≤ m ≤ 10 5 1\le m\le 10^51≤m≤1051 ≤ a , b ≤ n 1\le a,b\le n1≤a,b≤n且a ≠ b a\neq bab1 ≤ u i , v i ≤ n 1\le u_i,v_i\le n1≤ui​,vi​≤n1 ≤ 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的节点均为安全节点将其奶酪价值相加得到答案。代码实现#includebits/stdc.husingnamespacestd;typedeflonglongll;constintMAXN100010;constll INF1e18;intn,m,a,b;ll c[MAXN];// 每个节点的奶酪价值vectorpairint,lladj[MAXN];// 邻接表存储图pair为(邻居节点, 边权)ll dist_cat[MAXN];// 猫从窝点a到每个节点的最短时间ll H[MAXN];// H[u]表示节点u的安全值即从u到b的安全路径中的最小时间差// 从起点start猫窝a运行Dijkstra算法计算猫到每个节点的最短时间voiddijkstra(intstart){for(inti1;in;i)dist_cat[i]INF;dist_cat[start]0;// 使用最小堆按距离从小到大处理priority_queuepairll,int,vectorpairll,int,greaterpairll,intpq;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]dw){dist_cat[v]dw;pq.push({dist_cat[v],v});}}}}// 从老鼠洞b开始计算安全节点及其H值voidcompute_H(){for(inti1;in;i)H[i]-1;// -1表示尚未确定是否安全H[b]dist_cat[b];// 老鼠洞b本身是安全的其H值为猫到b的最短时间// 使用最大堆按H值从大到小处理以便优先扩展H值大的节点priority_queuepairll,intpq;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(wh_val){// 计算u的候选H值min(猫到u的最短时间, H[v] - w)ll candmin(dist_cat[u],h_val-w);// 只有候选值大于0才表示u可能安全并且大于当前记录的H值才更新if(cand0candH[u]){H[u]cand;pq.push({H[u],u});}}}}}intmain(){ios::sync_with_stdio(false);cin.tie(0);// 读入数据cinnm;cinab;for(inti1;in;i)cinc[i];for(inti0;im;i){intu,v;ll w;cinuvw;adj[u].push_back({v,w});adj[v].push_back({u,w});// 无向图添加双向边}// 步骤1计算猫从窝点a到所有节点的最短时间dijkstra(a);// 步骤2从老鼠洞b开始计算所有安全节点compute_H();// 步骤3累加所有安全节点的奶酪价值ll ans0;for(inti1;in;i){if(H[i]0){// H[i] 0 表示节点i是安全的ansc[i];}}coutansendl;return0;}功能分析时间复杂度Dijkstra 算法O((nm) log n)。安全节点扩展每个节点和边可能被多次检查但每个节点最多被更新一次取最大 H 值整体O((nm) log n)。总复杂度O((nm) log n)可处理 n, m ≤10 5 10^5105的数据规模。空间复杂度使用邻接表存储图O(nm)。数组dist_cat、H、cO(n)。优先队列O(n)。总空间复杂度O(nm)。注意事项使用long long存储边权和距离避免溢出。安全节点必须满足H[i] 0排除猫窝a其dist_cat[a] 0。扩展时使用最大堆优先处理H值大的节点以最大化安全区域的扩展。各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}1、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html2、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.html4、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}