P8817 [CSP-S 2022] 假期计划

#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
#define ll long long
#define pii pair<ll,ll>
#define fir first
#define sec second
#define mp make_pair
const ll N = 4600 , M = 50000 + 123 ;
ll n , m , k , val [ N * 2 ] ;
ll cnt , h [ M * 2 ] , nt [ M << 1 ] , to [ M << 1 ] ;
ll load [ N ] [ N ] ;
void add ( ll x , ll y )
{
	nt [ ++ cnt ] = h [ x ] ;
	h [ x ] = cnt ;
	to [ cnt ] = y ;
}
void link ( int x , int y ) { add ( x , y ) ; add ( y , x ) ; }
void bfs ( ll st ){
	queue < ll > q;
	load [ st ] [ st ] = 0 ;
	q . push ( st ) ;
	while ( ! q . empty () ) {
		ll x = q . front () ; q . pop ();
		if ( load [ st ] [ x ] == k ) continue;
		for ( ll i = h [ x ] ; i ; i = nt [ i ] ) {
			ll y = to [ i ] ;
			if ( load [ st ] [ y ] >= 0 ) continue;
			load [ st ] [ y ] = load [ st ] [ x ] + 1 ;
			q . push ( y ) ;
		}
	}
}
pii a [ N * 2 ] , b [ N * 2 ] , c [ N * 2 ] ;
void update ( ll fm , ll to , ll w ){
	if ( a [ to ] . fir < w ) {
		c [ to ] = b [ to ] ;
		b [ to ] = a [ to ] ;
		a [ to ] = mp ( w , fm ) ;
		return;
	}
	if ( b [ to ] . fir < w ) {
		c [ to ] = b [ to ] ;
		b [ to ] = mp ( w , fm ) ;
		return;
	}
	if ( c [ to ] . fir < w ) {
		c [ to ] = mp ( w , fm ) ;
		return;
	}
}
bool different ( ll aa , ll bb , ll cc , ll dd ) {
	if ( aa == 0 || bb == 0 ) return false;
	ll s [ 4 ] = { aa , bb , cc , dd } ;
	sort ( s , s + 4 ) ;
	if ( s [ 0 ] == s [ 1 ] || s [ 1 ] == s [ 2 ] || s [ 2 ] == s [ 3 ] ) 
		return false;
	return true;
}
ll dist ( ll x , ll y ) {
	ll rhs = -( 1 << 30 ) ;
	if ( different (  a [ x ] . sec , a [ y ] . sec , x , y ) ) 
	rhs = max ( rhs , a [ x ] . fir + a [ y ] . fir ) ;

	if ( different (  a [ x ] . sec , b [ y ] . sec , x , y ) ) 
	rhs = max ( rhs , a [ x ] . fir + b [ y ] . fir ) ;

	if ( different (  a [ x ] . sec , c [ y ] . sec , x , y ) ) 
	rhs = max ( rhs , a [ x ] . fir + c [ y ] . fir ) ;

	if ( different (  b [ x ] . sec , a [ y ] . sec , x , y ) ) 
	rhs = max ( rhs , b [ x ] . fir + a [ y ] . fir ) ;

	if ( different (  b [ x ] . sec , b [ y ] . sec , x , y ) ) 
	rhs = max ( rhs , b [ x ] . fir + b [ y ] . fir ) ;

	if ( different (  b [ x ] . sec , c [ y ] . sec , x , y ) ) 
	rhs = max ( rhs , b [ x ] . fir + c [ y ] . fir ) ;

	if ( different (  c [ x ] . sec , a [ y ] . sec , x , y ) ) 
	rhs = max ( rhs , c [ x ] . fir + a [ y ] . fir ) ;

	if ( different (  c [ x ] . sec , b [ y ] . sec , x , y ) ) 
	rhs = max ( rhs , c [ x ] . fir + b [ y ] . fir ) ;

	if ( different (  c [ x ] . sec , c [ y ] . sec , x , y ) ) 
	rhs = max ( rhs , c [ x ] . fir + c [ y ] . fir ) ;
	return rhs ;
}
void work () {
	for ( ll i = 2 ; i <= n ; i ++ ) {
		for ( ll j = 2 ; j <= n ; j ++ ) {
			if ( i == j ) continue;
			if ( load [ 1 ] [ i ] >= 0 && load [ i ] [ j ] >= 0 )
				update ( i , j , val [ i ] + val [ j ] ) ;
		}
	}
	ll ans = 0 ;
	for ( ll i = 2 ; i <= n ; i ++ ) 
	{
		for ( ll j = i + 1 ; j <= n ; j ++ ) 
		{
			if ( i == j ) continue;
			if ( load [ i ] [ j ] >= 0 )
				ans = max ( ans , dist ( i , j ) ) ;
		}
	}
	printf ( "%lld\n" , ans ) ;
}
int main () {
	memset ( load , -0x3f3f3f3f , sizeof ( load ) ) ;
	cin >> n >> m >> k ;
	k ++ ;
	for ( ll i = 2 ; i <= n ; i ++ ) {
		scanf ( "%lld" , & val [ i ] ) ;
	}
	for ( ll i = 0 ; i < m ; i ++ ) {
		static ll x , y ;
		scanf ( "%lld%lld" , & x , & y ) ; link ( x , y ) ;
	}
	for ( ll i = 1 ; i <= n ; i ++ ) {
		bfs ( i ) ;
	}
	work();
}