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 当⼀个点在最短路中出现两次 快!
05-12 14:43