Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## Re:bellman ford检查负圈, 注意M是双向边

Posted by tianqiong123 at 2019-09-10 23:10:32 on Problem 3259
In Reply To:bellman ford检查负圈, 注意M是双向边 Posted by:SmartChen at 2018-10-30 17:34:03
```> #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");
> 	}
> }
```

Followed by: