题解：瑞学堂 瑞瑞的体力回收路径

本文分享的必刷题目是从蓝桥云课、洛谷、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

【核心思想】

1. 问题分析：给定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问题，关键在于将"体力"作为状态维度，用二维最短路求解。

2. 算法选择：

   • Dijkstra 算法（状态扩展）：状态定义为( u , s ) (u, s)(u,s)，表示到达路口u uu且当前体力为s ss的最短通行时间
   • 小根堆优化：按通行时间升序的优先队列，保证每次取出当前最优状态
   • 体力约束处理：转移时检查n s = s + k i ns = s + k_ins=s+ki​，若n s < 0 ns < 0ns<0则不可行，若n s > H ns > Hns>H则截断为H HH

3. 关键步骤：

   • 初始化：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]t>dist[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_ins=s+ki​
       • 若n s < 0 ns < 0ns<0，跳过（体力不能为负）
       • 若n s > H ns > Hns>H，令n s = H ns = Hns=H（截断到上限）
       • 新时间n t = t + t i nt = t + t_int=t+ti​
       • 若n t < d i s t [ v ] [ n s ] nt < dist[v][ns]nt<dist[v][ns]，更新并入堆
   • 统计答案：遍历s ss从0 00到H HH，找dist[n][s]最小值；若相同则取s ss最大

4. 时间/空间复杂度：

   • 时间复杂度：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(nH+m)，dist数组、邻接表、优先队列

5. 状态扩展 Dijkstra 的核心思想：

   • 体力作为状态维度：将一维最短路扩展为二维状态( u , s ) (u, s)(u,s)，因为体力变化影响后续可行路径，必须纳入状态
   • 截断简化状态空间：体力上限H HH将无限状态空间压缩为有限空间s ∈ [ 0 , H ] s \in [0, H]s∈[0,H]，保证算法可终止
   • 体力非负约束剪枝：n s < 0 ns < 0ns<0时直接跳过，避免无效状态入队，减少搜索空间
   • 双目标优化：Dijkstra 保证通行时间最短；时间相同时通过最后遍历体力维度取最大，实现次优目标最大化
   • 适用于"路径代价 + 资源约束"类问题，核心在于将资源量化为状态维度，用多维 Dijkstra 求解带约束的最短路

【算法标签】

#Dijkstra

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;constintN=20005,INF=1e9;// N为路口最大数量，INF为极大值intn,m,S,H;// n为路口数，m为道路条数，S为初始体力，H为体力上限structEdge{intv,t,k;// v为目标路口，t为通行时间，k为能耗系数};vector<Edge>g[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.t>y.t;// 通行时间短的优先}// Dijkstra算法：状态为(路口, 体力)，求最短通行时间voiddijkstra(){memset(dist,0x3f,sizeof(dist));// 将所有距离初始化为极大值priority_queue<Node,vector<Node>,greater<Node>>pq;// 小根堆dist[1][S]=0;// 起点：路口1，初始体力S，通行时间为0pq.push({0,1,S});// 将初始状态入队while(!pq.empty())// 当队列不为空时继续{autox=pq.top();pq.pop();// 取出通行时间最小的状态intt=x.t,u=x.u,s=x.S;// 取出当前通行时间、路口、体力if(t>dist[u][s])// 如果该状态已被更优路径访问过，跳过continue;for(autox:g[u])// 遍历从当前路口u出发的所有道路{intns=s+x.k;// 计算经过该道路后的新体力值if(ns<0)// 如果体力变为负数，无法通过该道路continue;if(ns>H)// 如果体力超过上限Hns=H;// 体力维持在上限H，多余部分丢失intnt=t+x.t;// 计算新的累计通行时间// 如果找到到达目标路口v、体力为ns的更短路径if(nt<dist[x.v][ns]){dist[x.v][ns]=nt;// 更新最短通行时间pq.push({nt,x.v,ns});// 将新状态入队}}}}intmain(){cin>>n>>m>>S>>H;// 读入路口数、道路条数、初始体力、体力上限while(m--)// 读入m条有向道路{intu,v,k,t;cin>>u>>v>>t>>k;g[u].push_back({v,t,k});// 添加从u到v的道路}dijkstra();// 执行Dijkstra算法// 在所有到达路口n的状态中，找最短通行时间；时间相同时选体力最大的intminn=INF,maxn=-1;// minn记录最短通行时间，maxn记录对应的最大体力for(ints=0;s<=H;s++)// 遍历所有可能的体力值{if(dist[n][s]<minn)// 如果找到更短的通行时间{minn=dist[n][s];// 更新最短通行时间maxn=s;// 记录对应的体力值}elseif(dist[n][s]==minn&&s>maxn)// 如果时间相同但体力更大{maxn=s;// 更新最大体力}}if(minn==INF)// 如果无法到达路口ncout<<-1<<endl;// 输出-1elsecout<<minn<<" "<<maxn<<endl;// 输出最短通行时间和最大体力值return0;}

【运行结果】

2 2 5 10 1 2 10 3 1 2 20 8 10 8