Date:2019/11/1
坑点
输出板子的写法数组要初始化！！！！！ 多组输入：数组不清零，爆零两行泪每组数据建边的时候，tot|cnt要从0开始 只有负数建单向边，0建双向边spfa的结尾要return false即为不是负环
AC code
#include<bits/stdc++.h>
using namespace std
;
#define maxn 10000
int n
,m
,s
,cnt
;
int hd
[maxn
], dis
[2*maxn
];
int vis
[2*maxn
], ji
[2*maxn
];
struct Edge
{
int to
,nxt
,w
;
}edge
[2*maxn
];
void add(int u
,int v
,int w
){
cnt
++;
edge
[cnt
].to
= v
;
edge
[cnt
].w
= w
;
edge
[cnt
].nxt
= hd
[u
];
hd
[u
] = cnt
;
}
bool spfa(){
queue
<int> q
;
q
.push(1); dis
[1] =0;ji
[1]=1;vis
[1] = 1;
while(!q
.empty()){
int u
= q
.front();
q
.pop();
vis
[u
] = false;
for(int j
= hd
[u
]; j
!=-1;j
= edge
[j
].nxt
){
int v
= edge
[j
].to
;
if(dis
[v
] > dis
[u
] + edge
[j
].w
){
dis
[v
] = dis
[u
] + edge
[j
].w
;
ji
[v
] = ji
[u
] + 1;
if(ji
[v
] > n
){
return true;
}
if(!vis
[v
]){
vis
[v
] = true;
q
.push(v
);
}
}
}
}
return false;
}
int main(){
int T
;
scanf("%d",&T
);
while(T
--){
cnt
= 0;
scanf("%d %d",&n
,&m
);
for(int i
= 1;i
<= n
+5 ;i
++){
hd
[i
]=-1;
dis
[i
]=0x3f3f3f3f;
vis
[i
]=0;
ji
[i
]=0;
}
for(int i
= 1,fi
,gi
,wi
; i
<= m
; i
++){
scanf("%d %d %d",&fi
,&gi
,&wi
);
add(fi
,gi
,wi
);
if(wi
>=0) add(gi
,fi
,wi
);
}
if(spfa()) printf("YE5\n");
else printf("N0\n");
}
return 0;
}
KaTeX parse error: Undefined control sequence: \font at position 16: \to \color{red}\̲f̲o̲n̲t̲{Happy \:ending
