Rt,对于第 10 个点,如下代码会 TLE:
while(l!=r){
u=q[l], l++;
if(l==N) l=0;
vis[u]=0;
if(++cnt[u]>=n) {
cout<<"No";
return 0;
}
for(register int k=h[u];k;k=d[k].n){
v=d[k].b, c=d[k].c;
if(t[u]+c<t[v]&&!vis[v]){
t[v]=t[u]+c;
vis[v]=1;
q[r++]=v;
if(r==N) r=0;
}
}
}
如下代码能 AC :
while(l!=r){
u=q[l], l++;
if(l==N) l=0;
vis[u]=0;
for(register int k=h[u];k;k=d[k].n){
v=d[k].b, c=d[k].c;
if(t[u]+c<t[v]&&!vis[v]){
cnt[v]=max(cnt[v], cnt[u]+1);
if(cnt[v]>n) {
cout<<"No";
return 0;
}
t[v]=t[u]+c;
vis[v]=1;
q[r++]=v;
if(r==N) r=0;
}
}
}
而查看提交记录,dfs_spfa 快的飞起。请问第二种负环判断方式是否正确?而 dfs_spfa 是否实用?望解答,谢谢啦。