PTA L3-040 人生就像一场旅行 - 题解与完整代码 题目概述题目要求我们在一个带权无向图中找到从起点到其他城市的耗时或者费用/距离不超过给定阈值b的可达城市。如果有多条路线我们主要关心最短耗时且在最短耗时的前提下能够获得最大的旅行体验值心情/价值x。最终需要对于每个查询起点的要求输出所有可以在经费/时间b内到达的城市编号按编号递增顺序。在这些可达城市中输出能获得最大期望体验值的城市编号列表。如果没有任何城市可达则输出T_T。 解题思路本题的核心是多源最短路问题因为数据范围通常较小n一般在几百以内所以非常适合使用Floyd-Warshall 算法来计算任意两点之间的最短路和最大体验值。状态定义使用二维结构体数组dst[i][j]dst[i][j].w从城市i到城市j的最短距离 / 最小花费。初始值为无穷大。dst[i][j].x在保证花费最短的前提下从i到j的最大体验值。初始值为 0。图的初始化对于每个顶点iiidst[i][i].w 0, dst[i][i].x 0。读入边的时候注意保存重边中的最小耗时如果耗时相同再保存最大的体验值虽然本题代码中读入阶段只做了最简单的分离存储但 Floyd 的内部逻辑处理了它。Floyd 算法的状态转移 (fld函数)枚举中间节点kk起点i和终点j设当前经过kk的新耗时tmp dst[i][kk].w dst[kk][j].w;如果tmp b直接跳过因为此时已经超过了最大限制不符合题意且没必要更新这里有一个小的剪枝。如果发现更短的路径dst[i][j].w tmp则更新w并且将体验值x更新为两段体验值之和。如果发现距离相同dst[i][j].w tmp则比较体验值如果经过kk中转能获得更高的体验值dst[i][j].x dst[i][kk].x dst[kk][j].x则更新最大体验值。处理查询对于每次查询ask遍历所有城市i∈[1,n]i \in [1, n]i∈[1,n](i≠aski \neq askiask)。检查是否有满足条件的城市 (dst[i][ask].w b且不仅是无穷大)。输出符合条件的所有城市编号。维护一个最大体验值mx和一个ans数组如果当前遍历的符合条件的城市的体验值 mx清空ans放入iii并更新mx如果等于mx追加放入ans。最后输出ans数组即可。如果没有符合条件的城市输出T_T。 C 完整代码实现#includebits/stdc.h#defineintlonglongusingnamespacestd;constintN1e9;// 无穷大常量intb,n,m,k;// 定义节点结构体w表示距离/花费x表示附带的价值/体验structnode{intwN,x0;}dst[510][510];// Floyd-Warshall 求解多源最短路及最大附加值voidfld(){for(intkk1;kkn;kk){for(inti1;in;i){for(intj1;jn;j){inttmpdst[i][kk].wdst[kk][j].w;if(tmpb)continue;// 剪枝超过预算b直接不考虑// 如果发现更短的路径全面更新距离和体验值if(dst[i][j].wtmp){dst[i][j].wtmp;dst[j][i].wtmp;dst[i][j].xdst[i][kk].xdst[kk][j].x;dst[j][i].xdst[i][j].x;}// 如果距离相同则取体验值更大的elseif(dst[i][j].wtmp){if(dst[i][j].xdst[i][kk].xdst[kk][j].x){dst[i][j].xdst[i][kk].xdst[kk][j].x;dst[j][i].xdst[i][j].x;}}}}}}voidsolve(){cinbnmk;// 初始化对角线for(inti1;in;i){dst[i][i].w0;dst[i][i].x0;}// 读入边并初始化图for(inti1;im;i){intu,v,w,x;cinuvwx;// 注意此处如果存在重边代码采取的是简单的min/max预处理dst[u][v].wmin(dst[u][v].w,w);dst[u][v].xmax(dst[u][v].x,x);dst[v][u].wmin(dst[v][u].w,w);dst[v][u].xmax(dst[v][u].x,x);}// 跑一边 Floydfld();// 处理询问while(k--){intask;cinask;vectorintans;boolfl0;intmx-1;// 查找所有符合条件的城市for(inti1;in;i){if(iask)continue;if(dst[i][ask].wN)continue;// 不可达if(dst[i][ask].wb)continue;// 超过花费限制// 记录遍历到的合法城市if(!fl)fl1;elsecout ;couti;// 维护能获得的最大体验值if(dst[i][ask].xmx){ans.clear();mxdst[i][ask].x;ans.push_back(i);}elseif(dst[i][ask].xmx){ans.push_back(i);}}// 如果没有符合条件的城市输出 T_Tif(!fl){coutT_T\n;continue;}cout\n;// 输出拥有最大体验值的城市集合for(inti0;ians.size();i){coutans[i];if(i!ans.size()-1)cout ;}cout\n;}}signedmain(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);solve();return0;} 总结这道题是经典的带有限制条件的多源带权图求极值问题。利用Floyd算法可以很好地兼顾到边权的更替最秒的点在于在 Floyd 的内层加入tmp b的小剪枝来快速滤除无效状态。代码中同时开两个值w和x并在距离相同时使用x继续判断非常符合“第一关键字、第二关键字”的最短路套路逻辑清晰易懂