题目链接：

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

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

代码：

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 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
                 
                   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
                  
                    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
                   
                    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;}