请教一个问题，判断负环用什么办法比较好

一直以为spfa是最好的办法。直到做了这道题：
http://www.lydsy.com/JudgeOnline/problem.php?id=1486
这题是显然的二分+判负环。但我写的spfa会超时。
但这段代码能0.2s过
void dfs(int x){
vis[x] = 1; double cost = d[x], ncost;
rep(i, g[x].size()){
edge e = g[x][i];
ncost = cost + e.w;
if (ncost < d[e.v]) {
if (!vis[e.v]) {d[e.v] = ncost; dfs(e.v);}
else flag = 1;
if (flag) break;
}
}
vis[x] = 0;
}
bool test(double x){
rep(i, n) rep(j, g[i].size()) g[i][j].w = g[i][j].ow - x;
clr(d);
flag = 0;
rep(i, n) {dfs(i); if (flag) return true;}
return false;
}
思想是找到一个负环就结束，最好时间O(n) //不好意思滥用了大O记号
但似乎有爆栈的问题？
所以想请教下，一般判断负环用SPFA好还是直接搜好呢？谢谢