P8817 [CSP-S 2022] 假期计划

思路

因为所有边的边权都是 $1$ ，所以考虑用 Bfs 求全源最短路
$A,D$ 到 $1$ 的距离都 $ \le k+1 $，$ B,C$ 到 $ A,D $ 的距离都 $ \le k+1 $
枚举 $ B,C $，再根据枚到的 $B,C$，枚举符合条件的 $ A,D $，按照分数大小排序（$ B,C $ 是等价的）
因为对于每一个 $ B,C $，符合条件的 $ A,D $ 很多，取 $ max $ 的复杂度是 $ n^4 $，为了不超时，$ A,D $ 只保留最大的 $5$ 个即可

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF=1e9;

int n,m,k;
int w[2501],x,y;
int dis[2501][2501],maxi;
bool vis[2501];
queue <int> q;
vector <int> v[2501];
set <pair<int,int>> s[2501];

void Bfs(int st){
	memset(vis,0,sizeof(vis));
	memset(dis[st],0x3f,sizeof(dis[st]));
	
	dis[st][st]=0;
	q.push(st);
	
	while(!q.empty()){
		int top=q.front();
		q.pop();
		
		if(vis[top]) continue;
		else vis[top]=1;
		
		for(auto i:v[top]){
			if(dis[st][i]>dis[st][top]+1){
				dis[st][i]=dis[st][top]+1;
				q.push(i);
			}
		}
	}
}

signed main(){
//	freopen("1.in","r",stdin);
	cin>>n>>m>>k;
	for(int i=2;i<=n;i++)
		cin>>w[i];
	for(int i=1;i<=m;i++){
		cin>>x>>y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	for(int i=1;i<=n;i++) 
		Bfs(i);
	for(int i=2;i<=n;i++){		//枚举B,C
		for(int j=2;j<=n;j++){		//枚举A,D
			if(i==j) continue;
			if(dis[i][j]<=k+1 && dis[1][j]<=k+1)
				s[i].insert({w[j],j});
			if(s[i].size()>5)
				s[i].erase(s[i].begin());
		}
	}
	for(int i=2;i<=n;i++){		//枚举B
		for(int j=2;j<=n;j++){		//枚举C
			if(i==j || dis[i][j]>k+1) continue;
			for(auto p:s[i]){		//枚举A
				if(p.second==i || p.second==j) continue;
				for(auto q:s[j]){		//枚举D
					if(q.second==i || q.second==j || q.second==p.second) continue;
					maxi=max(maxi,w[i]+w[j]+p.first+q.first);
				}
			}
		}
	}
	cout<<maxi<<"\n";
}