WA 90pts 求调
查看原帖
WA 90pts 求调
742017
zhangxiao666楼主2023/7/18 15:49

rt

有没有好心的大佬帮忙调一下呀,再这样下去都要疯了qwq

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2505;
int n,m,k;
int ans=0;
int a[N];
vector<int> e[N];
int dis[N],f[N][10];
bool flag[N][N];
bool cmp(int x,int y)
{
	return a[x]>a[y];
}
void bfs(int x)
{
	queue<int> q; 
	memset(dis,-1,sizeof(dis));
	q.push(x); 
	dis[x]=0;
	while(!q.empty())
	{
		int h=q.front();
		q.pop();
		if(h!=x)
		{
			flag[x][h]=1;
			if(x!=1&&flag[1][h])
			{
				f[x][++f[x][0]]=h;
				sort(f[x]+1,f[x]+f[x][0]+1,cmp);
				if(f[x][0]>3) f[x][0]--;
			}
		}
		if(dis[h]==k+1) continue;
		for(int i=0;i<e[h].size();i++)
		{
			int now=e[h][i];
			if(dis[now]==-1)
			{
				dis[now]=dis[h]+1;
				q.push(now);
			}
		}
	}
} 
int max(int x,int y){if(x>y) return x;else return y;}
signed main()
{
	scanf("%lld%lld%lld",&n,&m,&k);
	for(int i=2;i<=n;i++)
	{
		scanf("%lld",&a[i]);
	}
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%lld%lld",&x,&y);
		e[x].push_back(y);
		e[y].push_back(x);
	}
	for(int i=1;i<=n;i++) bfs(i);
	for(int B=2;B<=n;B++)
	{
		for(int C=2;C<=n;C++)
		{
			if(flag[B][C])
			{
				for(int i=1;i<=f[B][0];i++)
				{
					int A=f[B][i];
					for(int j=1;j<=f[C][0];j++)
					{
						int D=f[C][i];
						if(A!=C&&B!=D&&A!=D)
						{
							ans=max(ans,a[A]+a[B]+a[C]+a[D]);
						}
					}
				}
			}
		}
	} 
	printf("%lld\n",ans);
	return 0;
}
2023/7/18 15:49
加载中...