负环指的是权值和为负数的环, 用 SPFA 加上 DFS 做比较方便, 如果用 BFS 来做就要便利太多点了.
题目描述
暴力枚举 / SPFA/Bellman-ford / 奇怪的贪心 / 超神搜索
输入输出格式
输入格式:
第一行一个正整数 T 表示数据组数, 对于每组数据:
第一行两个正整数 N M, 表示图有 N 个顶点, M 条边
接下来 M 行, 每行三个整数 a b w, 表示 a->b 有一条权值为 w 的边 (若 w<0 则为单向, 否则双向)
输出格式:
共 T 行. 对于每组数据, 存在负环则输出一行 "YE5"(不含引号), 否则输出一行 "N0"(不含引号).
来源: http://www.bubuko.com/infodetail-2568036.html