自动搬运

查看原文

来自洛谷，原作者为

	Drifting **

搬运于2025-08-24 21:42:16，当前版本为作者最后更新于2018-09-27 20:37:30，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这题居然没有用 $Floyd$ 判负环的题解...

(卡常极为痛苦，请开 $O2$ 优化)

因为代码极简单，直接看吧。

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int INF = 0x3f3f3f3f;
int T, n, m, W, dis[505][505];
inline int read()
{
	register int x = 0;
	char c = getchar();
	while (c < '0' || c > '9')
		c = getchar();
	while (c >= '0' && c <= '9')
	{
		x = (x << 3) + (x << 1) + c - '0';
		c = getchar();
	}
	return x;
}
bool check()
{
	for (register int k = 1; k <= n; k++)
		for (register int i = 1; i <= n; i++)
		{
			for (register int j = 1; j <= n; j++)
			{
				int res = dis[i][k] + dis[k][j];
				if (dis[i][j] > res)
					dis[i][j] = res;
			}
			if (dis[i][i] < 0)
				return 1;
		}
	return 0;
}
int main()
{
	T = read();
	while (T--)
	{
		n = read(), m = read(), W = read();
		for (register int i = 1; i <= n; i++)
			for (register int j = 1; j <= n; j++)
				dis[i][j] = INF;
		for (int i = 1; i <= m; i++)
		{
			int u = read(), v = read(), w = read();
			if (dis[u][v] > w)
				dis[u][v] = dis[v][u] = w;
		}
		for (int i = 1; i <= W; i++)
		{
			int u = read(), v = read(), w = read();
			dis[u][v] = -w;
		}
		if (check())
			printf("YES\n");
		else
			printf("NO\n");
	}
	return 0;
}