题解：洛谷 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#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=2505;// 最大节点数typedefpair<int,int>PII;// 存储(权重, 节点编号)对vector<int>e[N];// 邻接表存储图intw[N];// 存储每个节点的权重（w[1]=0，其他节点有正权重）intans;// 存储最终的最大四元组权重和intn,m,k;// n: 节点数, m: 边数, k: 最大中转次数限制intdist[N][N];// 存储任意两点间的最短距离set<PII>st[N];// 对于每个节点i，存储满足条件的节点集合，按权重排序// 广度优先搜索，计算从源点s到所有其他节点的最短距离voidbfs(ints){// 初始化距离数组for(inti=1;i<=n;i++){dist[s][i]=1e9;// 初始化为无穷大}dist[s][s]=0;// 源点到自己的距离为0queue<int>q;q.push(s);// 源点入队while(!q.empty()){intu=q.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(){// 输入节点数、边数、最大中转次数kcin>>n>>m>>k;// 输入每个节点的权重（从2到n，节点1的权重为0）for(inti=2;i<=n;i++){cin>>w[i];}// 输入图的边for(inti=1;i<=m;i++){intu,v;cin>>u>>v;e[u].push_back(v);e[v].push_back(u);}// 计算所有节点对之间的最短距离for(inti=1;i<=n;i++){bfs(i);}// 构建每个节点的候选集合// 对于每个节点i，收集满足以下条件的节点j：// 1. j != i// 2. 从i到j的距离 <= k+1// 3. 从起点1到j的距离 <= k+1for(inti=2;i<=n;i++){for(intj=2;j<=n;j++){if(j==i)// 跳过自身{continue;}// 检查距离限制条件if(dist[i][j]<=k+1&&dist[1][j]<=k+1){st[i].insert({w[j],j});// 按权重排序插入// 只保留权重最大的3个节点if(st[i].size()>3){st[i].erase(st[i].begin());// 删除最小的元素}}}}// 枚举所有可能的(b,c)对for(intb=2;b<=n;b++){for(intc=2;c<=n;c++){if(b!=c&&dist[b][c]<=k+1)// 满足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!=b&&d!=a){// 更新最大权重和ans=max(ans,w[b]+w[c]+wa+wd);}}}}}}}// 输出结果cout<<ans<<endl;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