95Pts

不知为什么WA，也不让下载数据

代码如下（有些冗长）：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
struct node{
	int next;
	int to;
	int v;
}edge[20010];
struct aa{
	long long val;
	int id;
}a[2501];
int n,m,k,d[2501][2501],head[2501],cnt=0;
long long f[2501][4];
queue<int> q;
void add(int x,int y,int z)
{
	edge[++cnt].next=head[x];
	head[x]=cnt;
	edge[cnt].to=y;
	edge[cnt].v=1;
}
void bfs(int s)
{
	for(int j=1;j<=n;j++)
	{
		d[s][j]=2147483646;
	}
	int vis[2501];
	d[s][s]=0;
	q.push(s);
	while(!q.empty())
	{
		int t=q.front();
		q.pop();
		if(d[s][t]+1>k+1) continue;
		for(int i=head[t];i;i=edge[i].next)
		{
			if(d[s][edge[i].to]>d[s][t]+1)
			{
				d[s][edge[i].to]=d[s][t]+1;
				q.push(edge[i].to);
			}
		}
	}
}
int main()
{
	cin>>n>>m>>k;
	for(int i=2;i<=n;i++)
	{
		cin>>a[i].val;
		a[i].id=i;
	 } 
	for(int i=1,x,y;i<=m;i++)
	{
		cin>>x>>y;
		add(x,y,1);
		add(y,x,1);
	}
	for(int i=1;i<=n;i++) bfs(i);
	aa max1,max2,max3,t1,t2;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=3;j++) f[i][j]=i;
	}
	for(int i=2;i<=n;i++)
	{
		max1.val=0,max2.val=0,max3.val=0,max1.id=0,max2.id=0,max3.id=0;
		for(int j=2;j<=n;j++)
		{
			if(d[i][j]!=2147483646&&j!=i&&d[1][j]!=2147483646)
			{
//				cout<<a[j].val<<" ";
				if(max1.val==0)
				{
					max1=a[j];
					continue;
				 } 
				else if(max2.val==0)
				{
					max2=a[j];
					continue;
				 } 
				else if(max3.val==0)
				{
					max3=a[j];
					continue;
				 } 
				if(a[j].val>max1.val)
				{
					t1=max1;
					t2=max2;
					max1=a[j];
					max2=t1;
					max3=t2;
					
				}
				else
				{
					if(a[j].val>max2.val)
					{
						t1=max2;
						max2=a[j];
						max3=t1;
					}
					else
					{
						if(a[j].val>max3.val) max3=a[j];
					}
				}
			}
		}
		t1=max1,t2=max2;
		if(max3.val>max2.val)
		{
			max2=max3;
			max3=t2;
		}
		if(max2.val>max1.val)
		{
			max1=max2;
			max2=t1;
		}
		t2=max2;
		if(max3.val>max2.val)
		{
			max2=max3;
			max3=t2;
		}
		f[i][1]=max1.id,f[i][2]=max2.id;f[i][3]=max3.id;
	}
	long long ans=0;
	for(int b=2;b<=n;b++)
	{
		for(int c=2;c<=n;c++)
		{
			if(d[b][c]==2147483646) continue;
			if(b==c) continue;
			for(int tota=1;tota<=3;tota++)
			{
				if(f[b][tota]==0) break;
				for(int totd=1;totd<=3;totd++)
				{
					if(f[c][totd]==0) break;
					if(f[b][tota]!=c&&f[c][totd]!=b&&f[b][tota]!=f[c][totd])
					{
						ans=max(ans,a[b].val+a[c].val+a[f[b][tota]].val+a[f[c][totd]].val);
						break;
					 } 
				}
			}
		}
		
	}
	cout<<ans;
	return 0;
}