bfs—spfa太慢，对于判负环
就只能用dfs—spfa
判负环的依据，具体会体现在code中
还有一道题也是判环
思路也是类似
#include#include #include #include using namespace std;struct node{ int point; int nxt; int weight;};int head[500000],tail;node line[500000];int dis[500000];int vis[500000];bool flag;void add(int a,int b,int c){ line[++tail].point=b; line[tail].nxt=head[a]; line[tail].weight=c; head[a]=tail;}void spfa(int x){ vis[x]=true; for(int i=head[x];i;i=line[i].nxt) { if(dis[line[i].point]>dis[x]+line[i].weight) { if(vis[line[i].point]||flag) { flag=true; return ; } dis[line[i].point]=dis[x]+line[i].weight; spfa(line[i].point); } } vis[x]=false;}int main(){ int t; scanf("%d",&t); for(int l=1;l<=t;l++) { int n,m; memset(vis,0,sizeof(vis)); memset(dis,0,sizeof(dis));//全置为0，这样正数边权就会被dfs时剪掉。只留下负数边权 memset(head,0,sizeof(head)); tail=0; flag=false; scanf("%d%d",&n,&m); int a,b,c; for(int i=1;i<=m;i++) { scanf("%d%d%d",&a,&b,&c); if(c>=0) { add(a,b,c); add(b,a,c); } else add(a,b,c); } for(int i=1;i<=n;i++) { spfa(i);//每个点一个跑一边 //不过为什么是正确的呢？ //如果和一个点与之相连的边都是正数，我们根本不能确定它是不是在负权环上 //但是如果一条边是负数，它有很大可能在负权边上。大体理会下[]~(￣▽￣)~* if(flag) break; } if(flag) printf("YE5\n"); else printf("N0\n"); }}/*3 41 2 21 3 42 3 13 1 -33 31 2 32 3 43 1 -8*/