题解：洛谷 P8817 [CSP-S 2022] 假期计划

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P8817 [CSP-S 2022] 假期计划 - 洛谷【题目描述】小熊的地图上有n nn个点其中编号为1 11的是它的家、编号为2 , 3 , … , n 2, 3, \ldots, n2,3,…,n的都是景点。部分点对之间有双向直达的公交线路。如果点x xx与z 1 z_1z1​、z 1 z_1z1​与z 2 z_2z2​、……、z k − 1 z_{k - 1}zk−1​与z k z_kzk​、z k z_kzk​与y yy之间均有直达的线路那么我们称x xx与y yy之间的行程可转车k kk次通达特别地如果点x xx与y yy之间有直达的线路则称可转车0 00次通达。很快就要放假了小熊计划从家出发去4 44个不同的景点游玩完成5 55段行程后回家家→ \to→景点 A→ \to→景点 B→ \to→景点 C→ \to→景点 D→ \to→家且每段行程最多转车k kk次。转车时经过的点没有任何限制既可以是家、也可以是景点还可以重复经过相同的点。例如在景点 A→ \to→景点 B 的这段行程中转车时经过的点可以是家、也可以是景点 C还可以是景点 D→ \to→家这段行程转车时经过的点。假设每个景点都有一个分数请帮小熊规划一个行程使得小熊访问的四个不同景点的分数之和最大。【输入】第一行包含三个整数n , m , k n, m, kn,m,k分别表示地图上点的个数、双向直达的点对数量、每段行程最多的转车次数。第二行包含n − 1 n - 1n−1个正整数分别表示编号为2 , 3 , … , n 2, 3, \ldots, n2,3,…,n的景点的分数。接下来m mm行每行包含两个正整数x , y x, yx,y表示点x xx和y yy之间有道路直接相连保证1 ≤ x , y ≤ n 1 \le x, y \le n1≤x,y≤n且没有重边自环。【输出】输出一个正整数表示小熊经过的4 44个不同景点的分数之和的最大值。【输入样例】8 8 1 9 7 1 8 2 3 6 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 1【输出样例】27【解题思路】【算法标签】#提高# #图的遍历-BFS#【代码详解】#includebits/stdc.husingnamespacestd;#defineintlonglongconstintN2505;// 最大节点数typedefpairint,intPII;// 存储(权重, 节点编号)对vectorinte[N];// 邻接表存储图intw[N];// 存储每个节点的权重w[1]0其他节点有正权重intans;// 存储最终的最大四元组权重和intn,m,k;// n: 节点数, m: 边数, k: 最大中转次数限制intdist[N][N];// 存储任意两点间的最短距离setPIIst[N];// 对于每个节点i存储满足条件的节点集合按权重排序// 广度优先搜索计算从源点s到所有其他节点的最短距离voidbfs(ints){// 初始化距离数组for(inti1;in;i){dist[s][i]1e9;// 初始化为无穷大}dist[s][s]0;// 源点到自己的距离为0queueintq;q.push(s);// 源点入队while(!q.empty()){intuq.front();q.pop();// 遍历所有邻居节点for(autov:e[u]){// 如果通过u到v的距离更短则更新if(dist[s][v]dist[s][u]1){dist[s][v]dist[s][u]1;q.push(v);}}}}signedmain(){// 输入节点数、边数、最大中转次数kcinnmk;// 输入每个节点的权重从2到n节点1的权重为0for(inti2;in;i){cinw[i];}// 输入图的边for(inti1;im;i){intu,v;cinuv;e[u].push_back(v);e[v].push_back(u);}// 计算所有节点对之间的最短距离for(inti1;in;i){bfs(i);}// 构建每个节点的候选集合// 对于每个节点i收集满足以下条件的节点j// 1. j ! i// 2. 从i到j的距离 k1// 3. 从起点1到j的距离 k1for(inti2;in;i){for(intj2;jn;j){if(ji)// 跳过自身{continue;}// 检查距离限制条件if(dist[i][j]k1dist[1][j]k1){st[i].insert({w[j],j});// 按权重排序插入// 只保留权重最大的3个节点if(st[i].size()3){st[i].erase(st[i].begin());// 删除最小的元素}}}}// 枚举所有可能的(b,c)对for(intb2;bn;b){for(intc2;cn;c){if(b!cdist[b][c]k1)// 满足b和c之间的距离限制{// 枚举节点b的候选节点afor(auto[wa,a]:st[b]){if(a!c)// 确保a不等于c{// 枚举节点c的候选节点dfor(auto[wd,d]:st[c]){// 确保d不等于a,b,cif(d!bd!a){// 更新最大权重和ansmax(ans,w[b]w[c]wawd);}}}}}}}// 输出结果coutansendl;return0;}【运行结果】8 8 1 9 7 1 8 2 3 6 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 1 27