rt

前三大用 set 实现

评测记录

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2500+5;
const int K=100;
const int M=10000+5;
const int INF=0x3f3f3f3f3f3f3f3f;

int n,m,k;
int ans=-INF;
bool vis[N][N];

struct Edge{
	int to,w,nxt;
}e[M*2];int tot,head[M*2];

inline void addedge(int u,int v,int w)
{e[++tot].to=v;e[tot].w=w;e[tot].nxt=head[u];head[u]=tot;}

int w[N];

int ck[N],sept[N];
void bfs(int s)
{
	memset(ck,0,sizeof(ck));
	memset(sept,0,sizeof(sept));
	queue<int> q;
	sept[s]=0;
	q.push(s);
	while(!q.empty())
	{
		int now=q.front();q.pop();
		if(ck[now]) continue;
		ck[now]=1;
		if(sept[now]>=k) break;
		for(int i=head[now];i;i=e[i].nxt)
		{
			int to=e[i].to;
			sept[to]=sept[now]+1;
			vis[s][to]=1;
			q.push(to);
		}
	}
}

set<pair<int, int> > s[N]; 

signed main()
{
	clock_t st=clock();
	srand(time(0));
	cin>>n>>m>>k;
	k++;
	for(int i=2;i<=n;++i)
		cin>>w[i];
	for(int i=1,u,v;i<=m;++i)
	{
		cin>>u>>v;
		addedge(u,v,1);addedge(v,u,1);
	}
	for(int i=1;i<=n;++i)
		bfs(i);
//	for(int i=1;i<=n;++i)
//	{
//		for(int j=1;j<=n;++j)
//			cout<<vis[i][j]<<" ";
//		cout<<endl;
//	}
	//if(clock()-st>1.98*CLOCKS_PER_SEC)break;
	for(int i=2;i<=n;++i)
		for(int j=2;j<=n;++j)
		{
			if(i==j) continue;
			if(vis[i][j] && vis[j][1]) s[i].insert(make_pair(w[j],j));
			if(s[i].size()>3) s[i].erase(s[i].begin());
		}//set按点权排序求出对于每个i有i->j->1的前三大路径 
	for(int b=2;b<=n;++b)
		for(int c=2;c<=n;++c)
			if(vis[b][c] && b!=c)
				for(auto a:s[b])
					if(a.second!=b && a.second!=c)
						for(auto d:s[c])
							if(d.second!=b && d.second!=c && d.second!=a.second)
								ans=max(ans,w[b]+w[c]+w[a.second]+w[d.second]);
	cout<<ans<<endl;
	return 0;
}