#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std; 
#define MAXN 510
#define MAXE 5210

int t, n, m, w, i, j, e;
int d[MAXN], ea[MAXE][3];

bool find_negative_loop(void){
	fill(d, d + n + 2, 0);
	for (i = 0; i < n; i++) {
		for (j = 0; j < e; j++) {
		//	printf("%d %d, %d %d %d\n", i, j, d[ea[j][1]], d[ea[j][0]] ,  d[ea[j][2]]);
			if (d[ea[j][1]] > d[ea[j][0]] + ea[j][2]) {
				d[ea[j][1]] = d[ea[j][0]] + ea[j][2];
				if (i == n - 1)
					return true;
			}
		}
	}
	return false;
}

int main() {
	scanf("%d", &t);
	while (t-- > 0) {
		scanf("%d %d %d", &n, &m, &w);
		m *= 2;
		e = m + w;
		for (i = 0; i < m; i++) {
			scanf("%d %d %d", &ea[i][0], &ea[i][1], &ea[i][2]);
			i++;
			ea[i][0] = ea[i - 1][1];
			ea[i][1] = ea[i - 1][0];
			ea[i][2] = ea[i - 1][2];
		}
		for (; i < e; i++) {
			scanf("%d %d %d", &ea[i][0], &ea[i][1], &ea[i][2]);
			ea[i][2] = -ea[i][2];
		}
		if (find_negative_loop())
			printf("YES\n");
		else
			printf("NO\n");
	}
}

• Re:bellman ford检查负圈, 注意M是双向边 (1133) tianqiong123 2019-09-10 23:10:32
• 多谢提醒 (4) tianqiong123 2019-09-10 23:11:14
• Re:bellman ford检查负圈, 注意M是双向边 (6) SZU_YUE 2024-07-16 07:34:22