@[zybnxy](/space/show?uid=51645)
```cpp
memset(dis,127,sizeof(dis));
//int下,0X7F7F7F7F相加会溢出
```
你有没有试过输出下面这个表达式的值:
`dis[z]>dis[x]+edge[i].w`
可能一直是`true`
by agicy @ 2019-01-30 19:13:47
@[卢安来](/space/show?uid=38502)
不是,改成了差不多$1e9$还是过不了
by zybnxy @ 2019-01-30 19:19:32
head 未清空、、、
by 稚名真白 @ 2019-01-30 19:23:37
好的我看错了
by 稚名真白 @ 2019-01-30 19:23:57
有说过从1开始走吗?
by 稚名真白 @ 2019-01-30 19:27:23
@[稚名真白](/space/show?uid=77807) 不然从哪里走。。
by zybnxy @ 2019-01-30 19:30:57
可能是队列没有清空?
参考一下我写的吧。
```cpp
#include<cstdio>
#include<cstring>
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++)
bool vis[501];
char buf[1000001],*p1=buf,*p2=buf;
int T,n,m,W,cnt,head[501],to[5201],w[5201],Next[5201],in[501],d[501];
int Q[4000001];
void Init(void);
void Add_Edge(int,int,int);
bool SPFA(int);
int read(void);
int main(void){
T=read();
while(T--){
Init();
if(!SPFA(1))
puts("YES");
else
puts("NO");
}
return 0;
}
void Init(void){
register int a,b,val;
cnt=0;
memset(head,0,sizeof(head));
n=read(),m=read(),W=read();
while(m--){
a=read(),b=read(),val=read();
Add_Edge(a,b,val);
Add_Edge(b,a,val);
}
while(W--){
a=read(),b=read(),val=read();
Add_Edge(a,b,-val);
}
return;
}
void Add_Edge(int f,int t,int val){
Next[++cnt]=head[f];
to[cnt]=t;
w[cnt]=val;
head[f]=cnt;
return;
}
bool SPFA(int s){
register int i,ID,head_,tail_;
memset(vis,false,sizeof(vis));
memset(in,0,sizeof(in));
memset(d,0X3F,sizeof(d));
Q[d[s]=head_=0]=s,tail_=1;
while(head_<tail_)
for(vis[ID=Q[head_++]]=false,i=head[ID];i;i=Next[i])
if(d[ID]+w[i]<d[to[i]])
if(d[to[i]]=d[ID]+w[i],!vis[to[i]])
if(vis[Q[tail_++]=to[i]]=true,++in[to[i]]>n)
return false;
return true;
}
inline int read(void){
register bool flag=true;
register char ch;
register int x=0;
do{ch=getchar();if(ch=='-')flag=!flag;}while(ch<'0'||'9'<ch);
while('0'<=ch&&ch<='9'){x=10*x+ch-'0';ch=getchar();};
return flag?x:-x;
}
```
by agicy @ 2019-01-30 19:32:00
@[zybnxy](/space/show?uid=51645) 任何点开始走,,,哪里能走出负环,就从哪里走
by 稚名真白 @ 2019-01-30 19:32:19
我是这么想的。。。。因为我的dfs好像就是这么走的
by 稚名真白 @ 2019-01-30 19:32:49
膜拜楼上大佬
by 明依 @ 2019-12-08 21:19:24