题目

题目背景

英文题面见此链接

题目描述

John 在他的农场中闲逛时发现了许多虫洞。虫洞可以看作一条十分奇特的有向边，并可以使你返回到过去的一个时刻（相对你进入虫洞之前）。

John 的每个农场有 $m$ 条小路（无向边）连接着 $n$ 块地（从 $1 \sim n$ 标号），并有 $w$ 个虫洞。

现在 John 想借助这些虫洞来回到过去（出发时刻之前），请你告诉他能办到吗。

输入格式

输入的第一行是一个整数 $T$ ，代表测试数据的组数。

每组测试数据的格式如下：

每组数据的第一行是三个用空格隔开的整数，分别代表农田的个数 $n$ ，小路的条数 $m$ ，以及虫洞的个数 $w$ 。

每组数据的第 $2$ 到第 $(m + 1)$ 行，每行有三个用空格隔开的整数 $u, v, p$ ，代表有一条连接 $u$ 与 $v$ 的小路，经过这条路需要花费 $p$ 的时间。

每组数据的第 $(m + 2)$ 到第 $(m + w + 1)$ 行，每行三个用空格隔开的整数 $u, v, p$ ，代表点 $u$ 存在一个虫洞，经过这个虫洞会到达点 $v$ ，并回到 $p$ 秒之前。

输出格式

对于每组测试数据，输出一行一个字符串，如果能回到出发时刻之前，则输出 YES，否则输出 NO。

输入输出样例

输入 #1

输出 #1

NO
YES

说明/提示

样例 2 解释

John 只需要沿着 $1 \rightarrow 2 \rightarrow 3 \rightarrow 1$ 的路径一直转圈即可，每转完一圈，时间就会减少一秒。

数据范围与约定

对于 $100\%$ 的数据， $1 \le T \le 5$ ， $1 \le n \le 500$ ， $1 \le m \le 2500$ ， $1 \le w \le 200$ ， $1 \le p \le 10^4$ 。

题解

这里其实很显然，就是要求有没有负环。这里我主要想说的是为什么在这道题当中，从任意一点出发跑SPFA都是可以判断的。首先，在没有虫洞的情况下，图是双向且连同的，那就意味着无论如何我们都可以在节点之间往返。所以，如果在某一点存在一个负环，那必定可以从其他任意一点到达，从而不断优化最短路，达到用SPFA判断负环的目的。

代码

下面是代码，其实就是裸的SPFA

#include <iostream>
#include <queue>
#include <cstring>
#define int long long

using namespace std;

const int maxm = 25005;
const int maxn = 5005;
const int maxw = 2005;

int n, m, T, w, ecnt = 2, head[maxn], dis[maxn], cnt[maxn];
bool in[maxn];
struct edge { int to, next, w; } g[(maxm << 1) + maxw];
void add_edge(int u, int v, int w) { g[ecnt] = (edge) { v, head[u], w }; head[u] = ecnt ++; }
struct node { int dis, pos; };

bool spfa() {
	for (int i = 1; i <= n; i ++) dis[i] = 2e9, in[i] = false;
	queue<node> q;
	dis[1] = 0; q.push((node) { dis[1], 1 });
	in[1] = true;
	cnt[1] = 0;
	while (!q.empty()) {
		int u = q.front().pos; q.pop(); in[u] = false;
		for (int e = head[u]; e; e = g[e].next) {
			int v = g[e].to;
			if (dis[v] > dis[u] + g[e].w) {
				dis[v] = dis[u] + g[e].w;
				cnt[v] = cnt[u] + 1;
				if (cnt[v] >= n) return true;
				if (!in[v]) {
					q.push((node) { dis[v], v });
					in[v] = true;
				}
			}
		}
	}
	return false;
}

signed main() {
	cin >> T;
	while (T --> 0) {
		cin >> n >> m >> w;
		ecnt = 2;
		memset(head, 0, sizeof(head));
		memset(g, 0, sizeof(g));
		for (int i = 1; i <= m; i ++) {
			int u, v, p; cin >> u >> v >> p;
			add_edge(u, v, p);
			add_edge(v, u, p); 
		}
		for (int i = 1; i <= w; i ++) {
			int u, v, p; cin >> u >> v >> p;
			add_edge(u, v, -p);
		}
		bool ans = spfa();
		cout << (ans ? "YES" : "NO") << endl;
	}
	return 0;
}

gyro永不抽风

P2850 [USACO06DEC]Wormholes G - SPFA求负环

题目