求大佬hack

先重建图再跑一个只走五步的SPFA最长路 在跑最长路的过程中判断路径上是否有重复的点 只走5步时间复杂度应该不会很高

但是洛谷 95 WA第5个点

Inf OJ 90 WA了两个点 有个点还很小

#include<bits/stdc++.h>
using namespace std;
const int N = 2.5e3+9,M = 2e7+9;
typedef long long ll;
typedef pair<int,int> PII;
int n,m,k;
ll ans,a[N];
int h[N],ver[M],ne[M],idx;
queue<PII>q;

struct E
{
    int u,v;
}e[M];

int tot;

void add(int u,int v)
{
    idx++,ver[idx] = v,ne[idx] = h[u],h[u] = idx;
}

bool vis[N];

void bfs(int x)
{
    q.push({x,0});
    vis[x] = 1;
    while(!q.empty())
    {
        int u = q.front().first,d = q.front().second;q.pop();
        if(d >= k+1)break;
        for(int i = h[u];i;i = ne[i])
        {
            int v = ver[i];
            if(vis[v])continue;
            if(d+1>1)e[++tot].u = x,e[tot].v = v;
            vis[v] = 1;
            q.push({v,d+1});
        }
    }
    while(q.size())q.pop();
}

ll dis[N][6];

bool inq[N][6];
int pre[N][6];

bool judge(int u,int d,int v)
{   
    if(d == 4 && v == 1)return 1;
    if(u == 0)return 1;
    if(u == v)return 0;
    return judge(pre[u][d],d-1,v);
}

void spfa()
{
    while(q.size())q.pop();
    q.push({1,0});
    inq[1][0] = 1;
    while(!q.empty())
    {
        int u = q.front().first,d = q.front().second;
        q.pop();inq[u][d] = 0;
        for(int i = h[u];i;i = ne[i])
        {
            int v = ver[i];
            if(!judge(u,d,v))continue;
            if(dis[v][d+1] < dis[u][d] + a[v])
            {
                pre[v][d+1] = u;
                dis[v][d+1] = dis[u][d] + a[v];
                if(!inq[v][d+1] && d+1 < 5)q.push({v,d+1}),inq[v][d+1] = 1;
            }
        }

    }
}

int main()
{

//  freopen("holiday.in","r",stdin);
//  freopen("holiday.out","w",stdout);

    scanf("%d%d%d",&n,&m,&k);
    for(int i = 2;i <= n;i++)scanf("%lld",&a[i]);

    for(int i = 1;i <= m;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v),add(v,u);
    }

    for(int i = 1;i <= n;i++)
    {
        memset(vis,0,sizeof(vis));
        bfs(i);
    }

    for(int i = 1;i <= tot;i++)add(e[i].u,e[i].v);

    spfa();

    printf("%lld",dis[1][5]);
    return 0;
}