题目链接：

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=499

题意：就是推断图中有无负环

SPFA,某个节点入队次数大于n就是有负环。

代码：

#include <iostream>

#include <stdio.h>

#include <string.h>

#include <algorithm>

#include <math.h>

#include <string>

#include <set>

#include <queue>

#include <stack>

#include <vector>

#include <malloc.h>

using namespace std;

const int MAXN = 41000;

const int INF = 0x3f3f3f3f;

struct Edge

{

    int v;

    int cost;

    Edge(int _v = 0, int _cost = 0)

    {

        v = _v;

        cost = _cost;

    }

};

vector<Edge> E[MAXN];

void addedge(int u, int v, int cost)

{

    E[u].push_back(Edge(v, cost));

}

bool vis[MAXN];

int cnt[MAXN];//记录入队列的次数

int dist[MAXN];

////////////////

bool SPFA(int start, int n)

{

    memset(vis, false, sizeof(vis));

    memset(cnt, 0, sizeof(cnt));

    for (int i = 0; i <= n; i++) dist[i] = INF;

    vis[start] = true;

    dist[start] = 0;

    queue<int> que;

    while (!que.empty()) que.pop();

    que.push(start);

    cnt[start] = 1;

    while (!que.empty())

    {

        int u = que.front(); que.pop();

        vis[u] = false;

        for (int i = 0; i<E[u].size(); i++)

        {

            int v = E[u][i].v;

            if (dist[v]>dist[u] + E[u][i].cost)

            {

                dist[v] = dist[u] + E[u][i].cost;

                if (!vis[v])

                {

                    vis[v] = true;

                    que.push(v);

                    cnt[v]++;

                    if (cnt[v] > n) return false;

                }

            }

        }

    }

    return true;

}

int n, m;

int a, b, c;

int main()

{

    int t;

    scanf("%d",&t);

    while (t--)

    {

        scanf("%d%d",&n,&m);

        for (int i = 0; i <= n; i++) E[i].clear();

        while (m--)

        {

            scanf("%d%d%d", &a, &b, &c);

            addedge(a, b, c);

            //addedge(b, a, c);

        }

        if (!SPFA(0, n)) puts("possible");

        else puts("not possible");

    }

    return 0;

}