@[Snoopydog](/space/show?uid=109416)
您好像说错了，
应该是如果能够松弛当前点并且当前点还在栈中，那图中存在负环
这是因为在一个无负环的图中从起点到任意一个点最短距离经过的点最多只有 n 个
by Edward_Elric @ 2019-02-16 21:41:31
@[Snoopydog](/space/show?uid=109416)
如果想过本题的话，放弃DFS吧
这个题吃饱了没事干专卡DFS
by CreeperLordVader @ 2019-02-16 21:43:17
@[法兰西万岁](/space/show?uid=58707)
但是dalao，我想请问一下，但是重复走也可能只是一个环啊，谢谢您的帮助
by 风说我活了 @ 2019-02-16 21:50:01
@[CreeperLordVader](/space/show?uid=68207)
谢谢您的提醒，我主要想用dfs判断是否存在负环，就这样判断。
```c
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 ;//不知道if这儿为什么这么写
}else{
DFS_SPFA(v);
}
}
}
vis[u]=false;
}
```
by 风说我活了 @ 2019-02-16 21:58:35
那可以写写洛谷上差分约束的题目
不卡DFS
by CreeperLordVader @ 2019-02-16 22:01:39
@[Snoopydog](/space/show?uid=109416) 不，并不是的在最短路中，是可以重复走松弛一个点是没错的，而你写的并不是重复走的意思，您可以理解一下
by Edward_Elric @ 2019-02-17 07:42:06
并不是说重复走了同一个点就是错的
比如边有n条边，1为起点n为重点
4
1 2 4
1 3 1
3 2 1
2 4 1
那么根据你建边的顺序，2是会进栈两次的，而不会存在负环，虽然您的程序是对的，但思想错了
by Edward_Elric @ 2019-02-17 07:45:50
@[法兰西万岁](/space/show?uid=58707)
哦，我懂了，是不是判断自环其实不用加判断是否可以对当前节点进行松弛操作，自环的话只需要枚举节点所有的出边，再判断是否访问过，访问过就有自环。而负环是能进行松弛，spfa每次松弛是减小距离，等于走回去的路径是个负数，就存在负环。
by 风说我活了 @ 2019-02-17 08:10:03