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 <string.h>
#include <queue>
using namespace std;
//#define LOCAL

struct
{
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/