80pts爆掉7个点求助

/*
找到一条路径1-A-B-C-D-1构成环
由于是无向图，根据环的对称性，可以拆成1-A-B和C-D-1（1-D-C）两条路径
1点是确定的，接下来只需要枚举B,C两点找最大值；
当B点是定点，A点就好求了：满足题意的点中找权值最大的点
注意：考虑到A点可能与D,C两点重合，因此需要求出前三大的1-A-B路径
即A与1、B相连且距离<=k+1的所有点中，点值最大的前三个
预处理b[i][3]记录与1和i相连{点值最大}的前三个点，考虑大根堆或直接分类讨论或排序（注意记录的是点）
转成k次，即两点间长度为k+1，就是要满足任意两点距离<=k+1
*/
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
int k,n,m;
long long w[3000];  //点的权值,w[1]=0
vector<int> e[3000];  //存每条边桐乡的下一个点,见一个邻接表
long long ans;
int dis[2600][2600];  //dis[i][j]表示从i点到j点的最短距离
int b[2600][5];
void bfs(int s)  //求s点到其他点的距离
{
    for(int i=1;i<=n;i++) dis[s][i]=-1;    //在这里初始化能优化时间
    queue<int> q;
    q.push(s);
    dis[s][s]=0;
    while(!q.empty())
    {
        int t=q.front();  
        q.pop();
        if(dis[s][t]>=k+1) continue;  //题目限定两点间的直接距离<=k+1，其他都视为无法到达（注意是>=k+1）
        for(vector<int>::iterator it=e[t].begin();it!=e[t].end();it++)
            if(dis[s][*it]==-1)  //如果*it这个点还没有被更新，就更新并入队，因为逐层扩散，先扩散到的一定最短，不用再比较了
            {
                dis[s][*it]=dis[s][t]+1;
                q.push(*it);
            }
    }
}
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i=2;i<=n;i++)
        scanf("%lld",&w[i]);
    int u,v;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&u,&v);
        e[u].push_back(v);
        e[v].push_back(u);
    }
    //如果使用转乘，剩余次数减一，下一个点不加权值
    for(int i=1;i<=n;i++) bfs(i);  //每个点都bfs
    //预处理b[][](不需要再判断dis<=k了，因为>k已经被视为无法到达)
    for(int i=2;i<=n;i++)  //定下B
    {
        int p1=0,p2=0,p3=0;  //依次记录A的分数值最大，次大，次次大的点
        for(int j=2;j<=n;j++)  //枚举A
        {
            if(i==j) continue; //b[i][]!=i
            if(dis[1][j]==-1 || dis[j][i]==-1) continue;
            if(w[j]>w[p1]) p3=p2,p2=p1,p1=j;
            else if(w[j]>w[p2]) p3=p2,p2=j;
            else if(w[j]>w[p3]) p3=j;  //记录点的序号
        }
        b[i][0]=p1,b[i][1]=p2,b[i][2]=p3;
    }
    for(int i=2;i<n;i++)  //枚举B
        for(int j=i+1;j<=n;j++)  //枚举C（不妨设C>B）
        {
            if(dis[i][j]==-1) continue;   //大范围枚举一定注意要有路径
            for(int k=0;k<3;k++) 
                for(int l=0;l<3;l++)  //已知C!=B,已经判断b[i][]!=i,还要满足A!=C,D,1;C!=A,B,1
                    if(b[j][l]!=j && b[i][k]!=i && b[i][k]!=b[j][l] && b[i][k]!=1 && b[j][l]!=1 && b[i][k]!=j && b[j][l]!=i )  
                        ans=max( ans,w[i]+w[j]+w[b[i][k]]+w[b[j][l]] );
        }
    printf("%lld",ans);
}