【计蒜客】 闯关游戏 Spfa判断环

题目链接【计蒜客】 闯关游戏



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

题目描述

在这里插入图片描述


思路

参考spfa算法,将节点增加或减少的值作为路径长度,我们要做的是找到每个点到起点的最大路径。在之前的Spfa算法中,我们是要寻找最短路径,即 dist[u] + w[u][v] < dist[v] 则更新dist[v]。在此题中,我们需要寻找最长的那条路径;即 dist[u] + w[u][v] > dist[v],则需要更新dist[v]。在更新的过程中,若更新的某个点的最大路径为负数,说明不能到达此房间,不要入队。若最后不能到达目标点或者目标点的最大路径为负,则判断为No
注意:
在之前的最短路问题中,我们遇到负权值回路时,则其没有最短路(可以一直在负权值回路中绕圈子)。在此题中,我们类比,当最长路可以不断增加时,即存在正权值回路时,我们可以在这个圈子中一直绕。所以若有正环,说明可在此无限增加体力,可直接判断为Yes。

代码

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
#include <bits/stdc++.h>
using namespace std;

#define MAX_N 110
#define MAX_M 500050
#define INF 0x3f3f3f3f

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

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

void init(int n)
{
cnt = 0;
memset(head, -1, sizeof(head));
memset(vis, 0, sizeof(vis));
memset(num, 0, sizeof(num));
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++;
}

void Spfa(int n, int v)
{
queue<int> S;
S.push(v);
dist[v] = 100;
vis[v] = 1;
num[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[v] < edge[i].val + dist[k] && edge[i].val + dist[k] > 0)
{
dist[v] = edge[i].val + dist[k];
if(!vis[v])
{
S.push(v);
num[v]++;
if(num[v] >= n)
{
cout << "Yes";
return ;
}
}
}
}
}
if(dist[n] > 0)
cout << "Yes";
else
cout << "No";
}

int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
init(n);
for(int i = 1; i<=n; i++)
{
int val, m;
cin >> val >> m;
for(int j = 1; j<=m; j++)
{
int tmp;
cin >>tmp;
add(i, tmp, val);
}
}
Spfa(n, 1);
return 0;
}
-------------本文结束,感谢您的阅读!-------------