Extended Traffic LightOJ - 1074 spfa判断负环

//判断负环  在负环内的城市输出？

#include <iostream>

#include <queue>

#include <cstdio>

#include <algorithm>

#include <string.h>

#include <string>

using namespace std;

typedef long long LL;

const int N=4e5+;

int abc[];

int T,n,m,q;

int h[N],e[N],ne[N],w[N],idx;

int len(int u,int v){

    return (abc[v]-abc[u])*(abc[v]-abc[u])*(abc[v]-abc[u]);

}

void add(int a,int b)

{

    e[idx]=b;

    w[idx]=len(a,b);

    ne[idx]=h[a];

    h[a]=idx++;

}

int dist[],st[],times[],cycle[];

void spfa()

{

    memset(dist,,sizeof(dist));

    memset(st,,sizeof(st));

    memset(times,,sizeof(times));

    memset(cycle,,sizeof(cycle));

    queue<int>q;

    st[]=times[]=;

    dist[]=;

    q.push();

    while(q.size())

    {

        int u=q.front();

        q.pop();

        st[u]=;

        for(int i=h[u];~i;i=ne[i])

        {

            int v=e[i];

            if(cycle[v])

                continue;

            if(dist[v]-dist[u]>w[i])

            {

                dist[v]=dist[u]+w[i];

                if(!st[v])

                {

                    st[v]=;

                    times[v]++;

                    q.push(v);

                }

                if(times[v]>n)

                    cycle[v]=;

            }

        }

    }

}

int main()

{

    cin>>T;

    for(int t=;t<=T;t++)

    {

        idx=;

        memset(h,-,sizeof h);

        cin>>n;

        for(int i=;i<=n;i++)

            cin>>abc[i];

        cin>>m;

        int a,b;

        while(m--)

        {

            cin>>a>>b;

            add(a,b);

        }

        spfa();

        cin>>q;

        printf("Case %d:\n",t);

        while(q--)

        {

            cin>>a;

            if(dist[a]<||dist[a]>=(int)1e9||cycle[a])

                printf("?\n");

            else

                printf("%d\n",dist[a]);

        }

    }

}