POJ3259.Wormholes

题意:教学楼里有很多教室，这些教室由双向走廊连接。另外，还存在一些单向的秘密通道，通过它们可以回到过去。现在有N(1 <= N <= 500)个教室，编号1...N，M(1 <= M <= 2500)条走廊，和W(1 <= W <= 200)条秘密通道。
DY在养猫之余，还是一个时间旅行爱好者。她希望从一间教室出发，经过一些走廊和秘密通道，回到她出发之前的某个时间。
共有F(1 <= F <= 5)组数据。对每组数据，判断DY是否有回到过去的可能性。不存在耗时超过10,000秒的走廊，且不存在能带DY回到10,000秒之前的秘密通道。

分析:spfa求负环，一个点如果被>=n个点更新过，说明从1号到这个点存在一条负权回路。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>

using namespace std;
typedef long long LL;
const int N = 505;
const int M = 5500;

int h[N], e[M], ne[M], idx;
int w[M];
void add(int a, int b, int c)
{
	e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

int dist[N], q[N];
bool st[N];
int cnt[N];
int n;

int spfa(int s)
{
	memset(dist, 0x3f, sizeof dist);
	memset(st, 0, sizeof st);
	memset(cnt, 0, sizeof cnt);

	int hh = 0, tt = 1;
	q[0] = s;
	st[s] = true;
	dist[s] = 0;
	while (hh != tt)
	{
		int t = q[hh++];
		if (hh == N) hh = 0;
		st[t] = false;

		for (int i = h[t]; i != -1; i = ne[i])
		{
			int j = e[i];

			if (dist[j] > dist[t] + w[i])
			{
				dist[j] = dist[t] + w[i];
				cnt[j] = cnt[t] + 1;
				if (cnt[j] >= n) return true;
				if (st[j] == false)
				{
					q[tt++] = j;
					if (tt == N) tt = 0;
					st[j] = true;
				}
			}
		}
	}

	return false;
}

int main()
{
	int f;
	scanf("%d", &f);

	while (f--)
	{		
		int m, w;
		scanf("%d%d%d", &n, &m, &w);

		memset(h, -1, sizeof h);
		idx = 0;

		int s, e, t;
		for (int i = 1; i <= m; ++i)
		{
			scanf("%d%d%d", &s, &e, &t);
			add(s, e, t), add(e, s, t);
		}

		for (int i = 1; i <= w; ++i)
		{
			scanf("%d%d%d", &s, &e, &t);
			add(s, e, -t);
		}

		bool has = spfa(1);

		if (has)
			cout << "YES" << endl;
		else
			cout << "NO" << endl;

	}
	

	return 0;
}

POJ3259.Wormholes

原文：https://www.cnblogs.com/pixel-Teee/p/13236076.html