#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<ctime>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=2500+10;
const int MAXM=1e4+10;
int dis[MAXN],lst_dis[MAXN];
int n,m,k,now;
queue <int> q;
vector <int> vec[MAXN],vec2[MAXN];
int a[MAXN];
bool vis[MAXN];
int lst[MAXN][6],lst_lst[MAXN][6];
void tst(){
	for(int i=1;i<=n;i++)
	{
		cout << i << "    ";
		for(int j=1;j<=5;j++)
		{
			printf("%2d ",lst[i][j]);
		}
		cout << "   " << dis[i] << endl;
	}
	printf("\n");
}
void clear_queue(){
	while(!q.empty())
	{
		q.pop();
	}
}
void Bfs1(int start){
	memset(vis,false,sizeof(vis));
	clear_queue();
	q.push(start);
	vis[start]=1;
	for(int I=0;I<=k;I++)
	{
		int siz=q.size();
		for(int i=1;i<=siz;i++)
		{
			int f=q.front();
			q.pop();
			for(int j=0;j<vec[f].size();j++)
			{
				int to=vec[f][j];
				if(vis[to]){
					continue;
				}
//				cout << start << " -> " << to << endl; 
				q.push(to);
				vec2[start].push_back(to);
				vis[to]=1;
			}
		}
	}
}
void bfs2(){
	memset(vis,false,sizeof(vis));
	for(int i=1;i<=n;i++)
	{
		lst_dis[i]=dis[i];
		for(int j=1;j<=now;j++)
		{
			lst_lst[i][j]=lst[i][j];
		}
	}
	memset(dis,0,sizeof(dis));
	memset(lst,-1,sizeof(lst));
	int siz=q.size();
	for(int i=1;i<=siz;i++)
	{
		int f=q.front();
		q.pop();
		for(int j=0;j<vec2[f].size();j++)
		{
			int to=vec2[f][j];
			if(!vis[to]){
				q.push(to);
			}
			vis[to]=1;
			if(dis[to]<lst_dis[f]+a[to]){
				bool flag=0;
				for(int J=1;J<now;J++)
				{
					if(lst_lst[f][J]==f){
						flag=1;
						break;
					}
				}
				if(flag){
					continue;
				}
				for(int J=1;J<now;J++)
				{
					lst[to][J]=lst_lst[f][J];
				}
				lst[to][now]=f;
				dis[to]=lst_dis[f]+a[to];
			}
		}
	}
}
void Bfs2(){
	clear_queue();
	q.push(1);
	for(now=1;now<=5;now++)
	{
		bfs2();
//		tst();
	}
}
int main(){
	scanf("%d%d%d",&n,&m,&k);
	for(int i=2;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		vec[x].push_back(y);
		vec[y].push_back(x);
	}
	for(int i=1;i<=n;i++)
	{
		Bfs1(i);
	}
	memset(lst,-1,sizeof(lst));
	Bfs2();
//	tst();
//	for(int i=1;i<=5;i++)
//	{
//		cout << lst[1][i] << " -> ";
//	}
//	cout << "1\n";
	printf("%d\n",dis[1]);
	return 0;
}
/*
7 9 0
1 1 1 2 3 4
1 2
2 3
3 4
1 5
1 6
1 7
5 4
6 4
7 4
*/

我的代码

ccf数据100

自测数据贼低