这个承认自己没看懂题目，一开始以为题意是形成环路之后走一圈不会产生负值就输出，原来就是判断负环，用SPFA很好用，运用队列，在判断负环的时候，用一个数组专门保存某个点的访问次数，超过了N次即可断定有负环（其实我觉得=N次了就可以断定了，当然这样是保险起见）。。。。别人还有用SPFA+DFS做的，还效率相当高，我还没怎么弄明白是怎么回事。。。还有，我突然想到讲最短路的时候说迪杰斯特拉不能用于有负权的图，这是为什么。。我还没想明白，先去睡觉吧。。。。
关于dijstla为什么不能有负权，昨晚躺下之后就想明白了，dijstla最大特性在于其把当前d值最小的点给灰化了，下次不用再访问了，而负权如果存在，将使得已经发生灰化的点，d值会变小，这样就不得不取消灰化，但一旦取消，dijstla就永远无法走到终点，（将一直在d值最小的那个点徘徊），因此spfa通过用队列把d值发生变化的点加进去，因而解决了这个问题这只是题外话，不用说太多
#include <iostream> #include <cstdio> #include <cstring> #include <queue> using namespace std; int u[2010],v[2010],w[2010],next[2010],first[1010]; int d[1010],vis[1010],num[1010]; int n,m,cnt,flag; void addedge(int a,int b,int c) { u[cnt]=a; v[cnt]=b; w[cnt]=c; next[cnt]=first[a]; first[a]=cnt++; } void spfa() { int i,j; flag=0; for (i=0;i<=n;i++) d[i]=(1<<30); memset(vis,0,sizeof vis); memset(num,0,sizeof num); d[0]=0; queue <int> q; q.push(0); vis[0]=1; while (!q.empty()) { int t=q.front(); q.pop(); vis[t]=0; for (j=first[t];j>=0;j=next[j]) { int newnode=v[j]; num[newnode]++; if (num[newnode]>n){ flag=1; return; } if (d[newnode]>d[t]+w[j]) { d[newnode]=d[t]+w[j]; //cout<<newnode<<" "<<d[newnode]<<endl; if (!vis[newnode]){ q.push(newnode); vis[newnode]=1; } } } } } int main() { int t,i,j; scanf("%d",&t); while (t--) { cnt=0; memset(first,-1,sizeof first); scanf("%d%d",&n,&m); int a,b,c; for (i=1;i<=m;i++){ scanf("%d%d%d",&a,&b,&c); addedge(a,b,c); } spfa(); if (!flag) puts("not possible"); else puts("possible"); } return 0; }