void DFS_SPFA(int u){
if(flag)
return;
vis[u]=true;
for(int i=head[u];i;i=edges[i].nxt){
if(flag)
return;
int v=edges[i].v;
if(d[u]+edges[i].t<d[v]){
d[v]=d[u]+edges[i].t;
if(vis[v]){
flag=true;
return;
}
else
DFS_SPFA(v);
}
}
vis[u]=false;
}
SPFA判负环
BFS 当⼀个点⼊队超过n次 则存在负环 慢!
DFS 当⼀个点在最短路中出现两次 快!