HDU 3259 Wormholes

HDU 3259 Wormholes

題意：就是給你一個n,m,t n代表有多少個點，m代表有多少個雙向的邊 t代表的是蟲洞，現在要你判讀是否還可以穿越到過去的點

蟲洞的意思是給你的邊是單向的，並且是負權值（輸入的時候是正數）

思路：是否可以穿越回過去的點，即有沒有負環，果斷套用模板,dijkstra算法不能檢測負環

AC代碼：

#include
#include
#include
#include
#include
#include
using namespace std;
#define maxn 520
const int INF = 0x3fffffff;
struct Edge
{
    int from,to,dist;
};
struct BellmanFord
{
    int n,m;
    vector edges;
    vector G[maxn];
    bool inq[maxn];
    int d[maxn];
    int p[maxn];
    int cnt[maxn];
    Edge e;
    void init(int n)
    {
        this->n=n;
        for(int i=0;iQ;
        memset(inq,0,sizeof(inq));
        memset(cnt,0,sizeof(cnt));
        for(int i=0;id[u]+e.dist)
                {
                    d[e.to]=d[u]+e.dist;
                    p[e.to]=G[u][i];
                    if(!inq[e.to])
                    {
                        Q.push(e.to);
                        inq[e.to]=true;
                        if(++cnt[e.to]>n)
                            return true;
                    }
                }
            }

        }
        return false;
    }
};
int main()
{
     int a,b,c,i,node,m,t,case1,k;
     bool j;
     scanf("%d",&case1);
     while(case1--)
     {
            scanf("%d %d %d",&node,&m,&t);
            if(node==0&&m==0)break;
            BellmanFord tu;
            tu.init(node);
            for(i=0;i