只错了民间数据 #7

#include<bits/stdc++.h>
#define maxn 10086
using namespace std;

struct edge {
  long long v, w;
};
struct node {
  long long dis, u;
  bool operator>(const node& a) const { return dis > a.dis; }
};

vector <edge> e[maxn];
long long dis[maxn][maxn], vis[maxn];
priority_queue<node, vector<node>, greater<node> > q;

void dijkstra(long long n, long long s) 
{
	memset(vis,0, sizeof(vis));
	for(long long i=1;i<=3000;i++) 
		dis[s][i]=999999999;
	dis[s][s] = 0;
	q.push({0, s});
	while(!q.empty())
	{
		long long u=q.top().u;
    	q.pop();
	    if(vis[u]) continue;
    	vis[u]=1;
   		for(auto ed :e[u]) 
		{
   		    long long v = ed.v, w = ed.w;
    	  	if (dis[s][v] > dis[s][u] + w) 
			{
   		  	 	dis[s][v] = dis[s][u] + w;
    	  	  	q.push({dis[s][v], v});
   	   		}
    	}
  	}
}
long long n,m,k,i,j,p[maxn],uu[maxn],vv[maxn],l,fi[5][maxn],fn[5][maxn],ans;
int main()
{
	cin>>n>>m>>k;
	for(i=2;i<=n;i++) cin>>p[i];
	for(i=1;i<=n;i++) fi[1][i]=fi[2][i]=fi[3][i]=-1;
	for(i=1;i<=m;i++)
	{
		cin>>uu[i]>>vv[i];
		e[uu[i]].push_back({vv[i],1});
		e[vv[i]].push_back({uu[i],1});
	}
	for(i=1;i<=n;i++)
		dijkstra(n,i);
	for(i=2;i<=n;i++)
	if(dis[1][i]<=k+1)
	{
		for(j=2;j<=n;j++)
		{
			if(j!=i&&dis[i][j]<=k+1)
			{
				if(p[i]>fi[1][j]){
					fi[3][j]=fi[2][j];fn[3][j]=fn[2][j];
					fi[2][j]=fi[1][j];fn[2][j]=fn[1][j];
					fi[1][j]=p[i];fn[1][j]=i;
					continue;
				}
				if(p[i]>fi[2][j]){
					fi[3][j]=fi[2][j];fn[3][j]=fn[2][j];
					fi[2][j]=p[i];fn[2][j]=i;
					continue;
				}
				if(p[i]>fi[3][j]){
					fi[3][j]=p[i];fn[3][j]=i;
				}
			}
		}
	}
	for(i=2;i<=n;i++)
		for(j=2;j<=n;j++)
		if(i!=j&&fi[1][i]!=-1&&fi[1][j]!=-1&&dis[i][j]<=k+1&&dis[i][j]!=0)
		{
			long long f=0;
			for(m=1;m<=3;m++)
				for(l=1;l<=3;l++)
				{
					if(fn[m][i]!=fn[l][j]&&fn[m][i]!=j&&i!=fn[l][j]&&fn[m][i]!=0&&fn[l][j]!=0)
					{
						f=max(f,fi[m][i]+fi[l][j]);
					}
				}
			ans=max(ans,f+p[i]+p[j]);
		}
	cout<<ans;
	return 0;
}