思路就是枚举bc,预处理ad,但是wa了

评测记录

#include<iostream> 
#include<cstring> 
#include<algorithm> 
#include<queue>
using namespace std; 
const int N=2510,M=20010; 
typedef long long LL;
LL n,m,k,ans,idx; 
LL h[N],e[M],ne[M],w[M]; 
LL m1[N],m2[N],m3[N]; 
bool st[N],vis[N][N]; 
void bfs(int u) 
{ 
	memset(st,false,sizeof st); 
	int cnt[N]; 
	queue<int> q;
	memset(cnt,0,sizeof cnt); 
	q.push(u),st[u]=true; 
	while(!q.empty()) 
	{ 
		int t=q.front();
		q.pop(); 
		for(int i=h[t];~i;i=ne[i]) 
		{ 
			int j=e[i];
			if(st[j]) continue; 
			else
			{ 
				vis[u][j]=vis[j][u]=true; 
				st[j]=true;
				if(cnt[t]<k) q.push(j); 
				cnt[j]=cnt[t]+1; 
				if(w[j]>=m1[u]&&vis[j][1]) m3[u]=m2[u],m2[u]=m1[u],m1[u]=j; 
				else if(w[j]>=m2[u]&&vis[j][1]) m3[u]=m2[u],m2[u]=j; 
				else if(w[j]>=m3[u]&&vis[j][1]) m3[u]=j; 
			}	 
		} 
	} 
	return; 
} 
void add(int a,int b)
{
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int main() 
{ 
	memset(h,-1,sizeof h); 
	cin>>n>>m>>k; 
	for(int i=2;i<=n;i++) cin>>w[i]; 
	for(int i=1,a,b;i<=m;i++) cin>>a>>b,add(a,b),add(b,a); 
	for(int i=1;i<=n;i++) bfs(i); 
	for(int i=2;i<=n;i++) 
		for(int j=2;j<=n;j++) 
		{ 
			int ret=w[i]+w[j]; 
			if(!vis[i][j]) continue; 
			if(m1[i]!=0&&m1[j]!=0&&m1[i]!=j&&m1[i]!=m1[j]&&m1[j]!=i) ans=max(ans,ret+w[m1[i]]+w[m1[j]]); 
			if(m1[i]!=0&&m2[j]!=0&&m1[i]!=j&&m1[i]!=m2[j]&&m2[j]!=i) ans=max(ans,ret+w[m1[i]]+w[m2[j]]); 
			if(m1[i]!=0&&m3[j]!=0&&m1[i]!=j&&m1[i]!=m3[j]&&m3[j]!=i) ans=max(ans,ret+w[m1[i]]+w[m3[j]]); 
			if(m2[i]!=0&&m1[j]!=0&&m2[i]!=j&&m2[i]!=m1[j]&&m1[j]!=i) ans=max(ans,ret+w[m2[i]]+w[m1[j]]); 
			if(m2[i]!=0&&m2[j]!=0&&m2[i]!=j&&m2[i]!=m2[j]&&m2[j]!=i) ans=max(ans,ret+w[m2[i]]+w[m2[j]]); 
			if(m2[i]!=0&&m3[j]!=0&&m2[i]!=j&&m2[i]!=m3[j]&&m3[j]!=i) ans=max(ans,ret+w[m2[i]]+w[m3[j]]); 
			if(m3[i]!=0&&m1[j]!=0&&m3[i]!=j&&m3[i]!=m1[j]&&m1[j]!=i) ans=max(ans,ret+w[m3[i]]+w[m1[j]]); 
			if(m3[i]!=0&&m2[j]!=0&&m3[i]!=j&&m3[i]!=m2[j]&&m2[j]!=i) ans=max(ans,ret+w[m3[i]]+w[m2[j]]); 
			if(m3[i]!=0&&m3[j]!=0&&m3[i]!=j&&m3[i]!=m3[j]&&m3[j]!=i) ans=max(ans,ret+w[m3[i]]+w[m3[j]]); 
		} 
	cout<<ans<<endl; 
}