本文主要是介绍P3385 【模板】负环 spfa判断负环，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
P3385 【模板】负环
题目描述
暴力枚举/SPFA/Bellman-ford/奇怪的贪心/超神搜索
寻找一个从顶点1所能到达的负环，负环定义为：一个边权之和为负的环。
输入输出格式
输入格式：
第一行一个正整数T表示数据组数，对于每组数据：
第一行两个正整数N M，表示图有N个顶点，M条边
接下来M行，每行三个整数a b w，表示a->b有一条权值为w的边（若w<0则为单向，否则双向）
输出格式：
共T行。对于每组数据，存在负环则输出一行"YE5"(不含引号)，否则输出一行"N0"(不含引号)。
输入输出样例
输入样例#1： 复制
2
3 4
1 2 2
1 3 4
2 3 1
3 1 -3
3 3
1 2 3
2 3 4
3 1 -8
输出样例#1： 复制
N0
YE5
说明
2000n≤2000
3000m≤3000
−10000≤w≤10000
10
这篇关于P3385 【模板】负环 spfa判断负环的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
