#include<bits/stdc++.h>
using namespace std;
long long n,m,k,tot,x,y,f[2505][2505],s[2505],h[2505],ans,fi[2505],se[2505],th[2505],p[7],p2[7];
struct node
{
    long long v,nxt;
}a[30005];
void add(long long x,long long y)
{
    tot++;
    a[tot].v=y;
    a[tot].nxt=h[x];
    h[x]=tot;
}
queue<long long>q;
void bfs(long long x)
{
    f[x][x]=-1;
    while(!q.empty())q.pop();
    q.push(x);
    while(!q.empty())
    {
        long long t=q.front();
        q.pop();
        for(int i=h[t];i;i=a[i].nxt)
        {
            if(f[x][a[i].v]>f[x][t]+1)
            {
                f[x][a[i].v]=f[x][t]+1;
                q.push(a[i].v); 
            }
        }
    }
}
bool cmp(long long x,long long y)
{
    if(s[x]==s[y])
    {
        return x<y;
    }
    return s[x]>s[y];
}
int main()
{
    scanf("%lld%lld%lld",&n,&m,&k);
    memset(f,127,sizeof(f));
    for(int i=2;i<=n;i++)
    {
        scanf("%lld",&s[i]);
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%lld%lld",&x,&y);
        add(y,x);
        add(x,y); 
    }
    for(int i=1;i<=n;i++)
    {
        bfs(i); 
    }
    for(int i=2;i<=n;i++)
    {
        for(int j=2;j<=n;j++)
        {
            if(i==j)continue;
            if(f[i][j]<=k&&f[1][j]<=k)
            {
                if(s[j]>s[fi[i]])
                {
                    th[i]=se[i];
                    se[i]=fi[i];
                    fi[i]=j;
                }
                else if(s[j]>s[se[i]])
                {
                    th[i]=se[i];
                    se[i]=j;                    
                }
                else if(s[j]>s[th[i]])
                {
                    th[i]=j;
                }

            }
        }
    //  cout<<fi[i]<<' '<<se[i]<<' '<<th[i]<<endl;
    }
    for(int i=2;i<=n;i++)
    { 
        if(fi[i]==0)continue; 
        for(int j=2;j<=n;j++)
        {
            if(i==j)continue;
            if(fi[j]==0)continue;
            if(f[i][j]>k)continue;
            long long mx=0;
            p[1]=fi[i];
            p[2]=se[i];
            p[3]=th[i];
            p2[1]=fi[j];
            p2[2]=se[j];
            p2[3]=th[j];
            for(int x=1;x<=3;x++)
            {
                if(p[x]==i||p[x]==j)continue;
                for(int y=1;y<=3;y++)
                {
                    if(p2[y]==i||p2[y]==j)continue;
                    if(p[x]==p2[y])continue;
                    mx=max(mx,s[p[x]]+s[p2[y]]);
                }
            }
            ans=max(ans,mx+s[i]+s[j]);
        }
    }
    printf("%lld",ans);
    return 0;
}

思路大概没问题。

用博客内容解释一下

讨论了一下只选3个点的情况，发现在选中一个点之后相当于给其他店附了权值，然后找最大和次大的。

4个点情况应该差不多，枚举中间两个点，再写个判断，感觉可行，于是开打