Wormholes SPFA算法

题目链接POJ-3259



kuangbin带你飞【专题六】 最短路

题目描述

农夫 FJ 有 N 块田地【编号 1…n】 (1<=N<=500)
田地间有 M 条路径 【双向】(1<= M <= 2500)
同时有 W 个孔洞,可以回到以前的一个时间点【单向】(1<= W <=200)
问:FJ 是否能在田地中遇到以前的自己


思路

田地间的双向路径加边,权值为正
孔洞间的单向路径加边,权值为负【可以回到以前】
判断有向图是否存在负环
因为如果存在了负数环,时间就会不停的减少,
那么 FJ 就可以回到以前更远的地方,肯定能遇到以前的自己的
运用Spfa算法,当某个点入队次数 >= 顶点数, 说明存在负权值回路,我们直接return true;否则dist数组里存储的就是单源最短路的距离;

代码

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
94
95
96
97
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;

#define MAX_N 550
#define MAX_M 5050
#define INF 0x3f3f3f3f

int head[MAX_M], vis[MAX_N], dist[MAX_N], cnt = 0, Count[MAX_N];

struct Node{
int to, val, next;
}edge[MAX_M];

void init(int n)
{
cnt = 0;
memset(Count, 0, sizeof(Count));
memset(head, -1, sizeof(head));
memset(vis, 0, sizeof(vis));
for(int i = 1; i<=n; i++)
{
dist[i] = INF;
}
}

void add(int x, int y, int val)
{
edge[cnt].to = y;
edge[cnt].val = val;
edge[cnt].next = head[x];
head[x] = cnt++;
}

bool Spfa(int n, int v)
{
queue<int> S;
S.push(v);
dist[v] = 0;
vis[v] = 1;
Count[v]++;
while(!S.empty())
{
int k = S.front();
S.pop();
vis[k] = 0;
for(int i = head[k]; i != -1; i = edge[i].next)
{
int v = edge[i].to;
if(dist[k] + edge[i].val < dist[v])
{
dist[v] = dist[k] + edge[i].val;
if(!vis[v])
{
S.push(v);
Count[v]++;
vis[v] = 1;
if(Count[v] >= n)
return true;
}
}
}
}
return false;
}

int main()
{
int T;
cin >> T;
while(T--)
{
int n, a, b;
cin >> n >> a >> b;
init(n);
for(int i = 1; i<=a; i++)//正权无向边
{
int x, y, val;
cin >> x >> y >> val;
add(x, y, val);
add(y, x, val);
}
for(int i = 1; i<=b; i++)
{
int x, y, val;
cin >> x >> y >> val;
add(x, y, -val);
}
if(Spfa(n, 1))
cout << "YES" << endl;
else
cout << "NO" << endl;
}
return 0;
}
-------------本文结束,感谢您的阅读!-------------