P11860 [CCC 2025 Senior] 熔岩路 / Floor is Lava题目背景译自 CCC 2025 Senior T4。本题满分为151515。题目描述你被困在一个炽热的地牢中。地牢由nnn个房间组成房间编号1∼n1\sim n1∼n。这些房间通过mmm条双向隧道相连第iii条双向隧道连接房间aia_iai和bib_ibi且地板被温度为cic_ici的熔岩覆盖。为了穿越熔岩隧道你穿着一双耐热靴子初始冷却等级为000。当你经过温度为ccc的熔岩时靴子的冷却等级必须恰好为ccc否则会被烫伤/冻伤。幸运的是当你站在一个房间里时你可以调整靴子的冷却等级每次增加或减少ddd需要支付ddd枚金币。你从房间111出发目标是到达房间nnn。到出口所需的最小金币花费是多少输入格式第一行两个正整数n,mn,mn,m。接下来mmm行每行三个正整数ai,bi,cia_i,b_i,c_iai,bi,ci。数据保证任意一对房间之间只有至多一条隧道从房间111可以到达任意一个其他的房间。输出格式输出一行一个非负整数表示答案。输入输出样例 #1输入 #15 7 1 2 3 2 3 2 1 3 6 3 4 3 4 5 7 2 4 1 2 5 10输出 #19说明/提示样例解释地牢的构造如上图所示。按照1→2→3→4→51\to 2\to 3\to 4\to 51→2→3→4→5的路线花费为∣3−0∣∣2−3∣∣3−2∣∣7−3∣9|3-0||2-3||3-2||7-3|9∣3−0∣∣2−3∣∣3−2∣∣7−3∣9可以证明是最优的。子任务对于100%100\%100%的数据保证1≤n,m≤2×1051\le n,m\le 2\times 10^51≤n,m≤2×1051≤ai,bi≤n1\le a_i,b_i\le n1≤ai,bi≤nai≠bia_i\neq b_iaibi1≤ci≤1091\le c_i\le 10^91≤ci≤109任意一对房间之间只有至多一条隧道;从房间111可以到达任意一个其他的房间。Subtask 0(0 points)\text{Subtask 0(0 points)}Subtask 0(0 points)样例。Subtask 1(2 points)\text{Subtask 1(2 points)}Subtask 1(2 points)mn−1mn-1mn−1。Subtask 2(4 points)\text{Subtask 2(4 points)}Subtask 2(4 points)1≤ci≤101\le c_i\le 101≤ci≤10。Subtask 3(4 points)\text{Subtask 3(4 points)}Subtask 3(4 points)每个房间至多连着555条隧道。Subtask 4(5 points)\text{Subtask 4(5 points)}Subtask 4(5 points)无特殊限制。C实现#includebits/stdc.husingnamespacestd;#defineintlonglong#definePIIpairlonglong,longlong#definexxfirst#defineyysecondconstintN4e510;//注意两边空间intn,m,dis[N];vectorPIIG[N],H[N];boolsure[N];priority_queuePII,vectorPII,greaterPIIq;voiddij(){memset(dis,0x3f,sizeof(dis));dis[0]0;q.push({0,0});while(!q.empty()){autouq.top();q.pop();if(sure[u.yy])continue;sure[u.yy]1;for(autov:H[u.yy]){if(dis[v.xx]dis[u.yy]v.yy){dis[v.xx]dis[u.yy]v.yy;q.push({dis[v.xx],v.xx});}}}}signedmain(){cinnm;for(inti1;im;i){intu,v,w;cinuvw;G[u].push_back({w,i});G[v].push_back({w,im});H[i].push_back({im,0});H[im].push_back({i,0});//正反边}for(inti1;in;i){sort(G[i].begin(),G[i].end());//边权排序for(intj0;jG[i].size()-1;j){H[G[i][j].yy].push_back({G[i][j1].yy,G[i][j1].xx-G[i][j].xx});H[G[i][j1].yy].push_back({G[i][j].yy,G[i][j1].xx-G[i][j].xx});}//加相邻的边}for(autoi:G[1])H[0].push_back({i.yy,i.xx});for(autoi:G[n])H[i.yy].push_back({mm1,0});//起点终点dij();coutdis[mm1];return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容