poj 3259 Wormholes 最短路

缘起

日常浪费生命 poj 3259 Wormholes

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
f个农场，每个农场n块玉米地，m条双向路径，w条单向路径（虫洞）（注意，不同农场的m和w未必一样）。单向虫洞路径是负值。农夫想知道自己能不能看到自己

【输入】
第一行是f, 然后后面是这f个农场的数据
对于每个农场, 第一行是 n,m,w(1 ≤ N ≤ 500,1 ≤ M ≤ 2500,1 ≤ W ≤ 200)
然后是M行, 每行(s,e,t)表示一条s和e之间的耗时t的双向道路
然后是w行，每行也是(s,e,t), 表示从s到e将倒流t时光的单向路径.

【输出】
对每个农场（本题也算是多样例了），输出YES或者NO表示FJ能不能看到自己.

【样例输入】
2
3 3 1
1 2 2
1 3 4
2 3 1
3 1 3
3 2 1
1 2 3
2 3 4
3 1 8

【样例输出】
NO
YES

【限制】
2s

【hint】
For farm 1, FJ cannot travel back in time. 
For farm 2, FJ could travel back in time by the cycle 1->2->3->1, arriving back at 
his starting location 1 second before he leaves. He could start from anywhere on the 
cycle to accomplish this.

spfa判断负权环是否存在, 没什么好说的. 裸题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
//#include "stdafx.h"

#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
//#define LOCAL

struct Arc
{
	int from,to,nxt,len;
	Arc(){}
	Arc(int from,int to,int nxt,int len):from(from),to(to),nxt(nxt),len(len){}
}g[5005];

int cnt,head[505],n,m,w,num[505],dis[505];
bool isinq[505];

void addArc(int from, int to, int len, int flag)
{
	g[cnt] = Arc(from, to, head[from], len*flag);
	head[from] = cnt++;
	if (flag==1) // 如果不是虫洞的话,则是双向边
	{
		g[cnt] = Arc(to,from,head[to], len);
		head[to] = cnt++;
	}
}

bool spfa() // 返回true表示存在负权环
{
	memset(isinq, 0, sizeof(isinq));
	memset(num, 0,sizeof(num));
	memset(dis, 0x3f, sizeof(dis));
	dis[1] = 0;
	queue<int> q;
	q.push(1);
	num[1] = 1;
	isinq[1] = true;
	while(!q.empty())
	{
		int front = q.front();
		q.pop();
		isinq[front] = 0;
		for (int h = head[front]; ~h; h = g[h].nxt)
		{
			int to = g[h].to;
			if (dis[to]>dis[front]+g[h].len)
			{
				dis[to] = dis[front]+g[h].len;
				if (!isinq[to])
				{
					isinq[to] = true;
					if (++num[to]>=n)
					{
						return true;
					}
					q.push(to);
				}
			}
		}
	}
	return false;
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	int  t;
	scanf("%d", &t);
	while(t--)
	{
		memset(head, -1, sizeof(head));
		cnt = 0;
		scanf("%d%d%d", &n, &m, &w);
		int x,y,z;
		while(m--)
		{
			scanf("%d%d%d", &x, &y, &z);
			addArc(x,y,z, 1);
		}
		while(w--)
		{
			scanf("%d%d%d", &x, &y, &z);
			addArc(x,y,z,-1);
		}
		spfa()?puts("YES"):puts("NO");
	}
	return 0;
}

ac情况

Status Accepted
Time 157ms
Memory 180kB
Length 1546
Lang C++
Submitted 2019-08-30 14:19:22
Shared
RemoteRunId 20818651

代码要是有不懂，可以参考【1】

参考

【1】https://yfsyfs.github.io/2019/08/23/poj-3169-Layout-%E6%9C%80%E7%9F%AD%E8%B7%AF/