本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】瑞学堂瑞瑞的体力回收路径【题目描述】瑞瑞所在的城市有n nn个路口和m mm条有向道路。每条道路连接两个路口并有一个非负的通行时间t i t_iti​。瑞瑞每天骑自行车从1 11号路口出发前往n nn号路口的学校上学。他的自行车有一个特殊的能量回收系统。每条道路都有一个能耗系数k i k_iki​。当瑞瑞经过能耗系数为k i k_iki​的道路时他的体力值会相应地变化k i k_iki​正数为恢复体力负数为消耗体力。瑞瑞的初始体力为S SS且体力值在任何时刻都不允许为负数所以他无法通过会导致体力变为负数的道路。同时体力值拥有上限H HH如果经过某条道路后体力值将要超过H HH则体力值将维持在上限H HH多出的部分将丢失。瑞瑞想知道从家到学校的最短通行时间是多少。如果有多条路径的通行时间相同他希望能选择到达学校时体力值最大的那条路径。【输入】第一行包含四个整数n , m , S , H n,m,S,Hn,m,S,H分别表示路口数、道路条数、初始体力值和体力上限。接下来的m mm行每行四个整数u i , v i , t i , k i u_i,v_i,t_i,k_iui​,vi​,ti​,ki​表示第i ii条从u i u_iui​到v i v_ivi​的有向道路其通行时间为t i t_iti​回收系数为k i k_iki​且u i u_iui​必定不等于v i v_ivi​。【输出】输出一行。如果无法从1 11号路口到达n nn号路口输出− 1 −1−1否则输出用空格分隔的两个整数最短的总通行时间和在该时间下到达n nn号路口时的最大体力值。【输入样例】2 2 5 10 1 2 10 3 1 2 20 8【输出样例】10 8【核心思想】问题分析给定n nn个路口、m mm条有向道路每条道路有通行时间t i t_iti​和能耗系数k i k_iki​正为恢复、负为消耗。初始体力为S SS体力上限为H HH体力不能为负、超过H HH则截断。求从路口1 11到路口n nn的最短通行时间若时间相同选到达时体力最大的路径。无法到达输出− 1 -1−1。这是一个状态扩展 Dijkstra问题关键在于将体力作为状态维度用二维最短路求解。算法选择Dijkstra 算法状态扩展状态定义为( u , s ) (u, s)(u,s)表示到达路口u uu且当前体力为s ss的最短通行时间小根堆优化按通行时间升序的优先队列保证每次取出当前最优状态体力约束处理转移时检查n s s k i ns s k_insski​若n s 0 ns 0ns0则不可行若n s H ns HnsH则截断为H HH关键步骤初始化dist[u][s]表示到达路口u uu且体力为s ss的最短通行时间初始化为∞ \infty∞起点入队dist[1][S] 0将( 0 , 1 , S ) (0, 1, S)(0,1,S)入堆Dijkstra 扩展循环取出堆顶( t , u , s ) (t, u, s)(t,u,s)若t d i s t [ u ] [ s ] t dist[u][s]tdist[u][s]则跳过遍历u uu的所有出边( v , t i , k i ) (v, t_i, k_i)(v,ti​,ki​)计算新体力n s s k i ns s k_insski​若n s 0 ns 0ns0跳过体力不能为负若n s H ns HnsH令n s H ns HnsH截断到上限新时间n t t t i nt t t_inttti​若n t d i s t [ v ] [ n s ] nt dist[v][ns]ntdist[v][ns]更新并入堆统计答案遍历s ss从0 00到H HH找dist[n][s]最小值若相同则取s ss最大时间/空间复杂度时间复杂度O ( m ⋅ H log ⁡ ( n H ) ) O(m \cdot H \log(nH))O(m⋅Hlog(nH))每个状态( u , s ) (u, s)(u,s)最多被更新一次每次堆操作O ( log ⁡ ( n H ) ) O(\log(nH))O(log(nH))空间复杂度O ( n H m ) O(nH m)O(nHm)dist数组、邻接表、优先队列状态扩展 Dijkstra 的核心思想体力作为状态维度将一维最短路扩展为二维状态( u , s ) (u, s)(u,s)因为体力变化影响后续可行路径必须纳入状态截断简化状态空间体力上限H HH将无限状态空间压缩为有限空间s ∈ [ 0 , H ] s \in [0, H]s∈[0,H]保证算法可终止体力非负约束剪枝n s 0 ns 0ns0时直接跳过避免无效状态入队减少搜索空间双目标优化Dijkstra 保证通行时间最短时间相同时通过最后遍历体力维度取最大实现次优目标最大化适用于路径代价 资源约束类问题核心在于将资源量化为状态维度用多维 Dijkstra 求解带约束的最短路【算法标签】#Dijkstra【代码详解】#includebits/stdc.husingnamespacestd;constintN20005,INF1e9;// N为路口最大数量INF为极大值intn,m,S,H;// n为路口数m为道路条数S为初始体力H为体力上限structEdge{intv,t,k;// v为目标路口t为通行时间k为能耗系数};vectorEdgeg[N];// g[u]存储从路口u出发的所有道路intdist[N][205];// dist[u][s]表示到达路口u且体力为s时的最短通行时间// 优先队列节点存储当前通行时间、当前路口、当前体力structNode{intt,u,S;// t为累计通行时间u为当前路口S为当前体力};// 重载大于运算符使priority_queue成为小根堆按通行时间升序booloperator(Node x,Node y){returnx.ty.t;// 通行时间短的优先}// Dijkstra算法状态为(路口, 体力)求最短通行时间voiddijkstra(){memset(dist,0x3f,sizeof(dist));// 将所有距离初始化为极大值priority_queueNode,vectorNode,greaterNodepq;// 小根堆dist[1][S]0;// 起点路口1初始体力S通行时间为0pq.push({0,1,S});// 将初始状态入队while(!pq.empty())// 当队列不为空时继续{autoxpq.top();pq.pop();// 取出通行时间最小的状态inttx.t,ux.u,sx.S;// 取出当前通行时间、路口、体力if(tdist[u][s])// 如果该状态已被更优路径访问过跳过continue;for(autox:g[u])// 遍历从当前路口u出发的所有道路{intnssx.k;// 计算经过该道路后的新体力值if(ns0)// 如果体力变为负数无法通过该道路continue;if(nsH)// 如果体力超过上限HnsH;// 体力维持在上限H多余部分丢失intnttx.t;// 计算新的累计通行时间// 如果找到到达目标路口v、体力为ns的更短路径if(ntdist[x.v][ns]){dist[x.v][ns]nt;// 更新最短通行时间pq.push({nt,x.v,ns});// 将新状态入队}}}}intmain(){cinnmSH;// 读入路口数、道路条数、初始体力、体力上限while(m--)// 读入m条有向道路{intu,v,k,t;cinuvtk;g[u].push_back({v,t,k});// 添加从u到v的道路}dijkstra();// 执行Dijkstra算法// 在所有到达路口n的状态中找最短通行时间时间相同时选体力最大的intminnINF,maxn-1;// minn记录最短通行时间maxn记录对应的最大体力for(ints0;sH;s)// 遍历所有可能的体力值{if(dist[n][s]minn)// 如果找到更短的通行时间{minndist[n][s];// 更新最短通行时间maxns;// 记录对应的体力值}elseif(dist[n][s]minnsmaxn)// 如果时间相同但体力更大{maxns;// 更新最大体力}}if(minnINF)// 如果无法到达路口ncout-1endl;// 输出-1elsecoutminn maxnendl;// 输出最短通行时间和最大体力值return0;}【运行结果】2 2 5 10 1 2 10 3 1 2 20 8 10 8