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