【計蒜客】 闖關遊戲 Spfa判斷環

題目連結：【計蒜客】 闖關遊戲

[kuangbin帶你飛【專題六】 最短路][2] ## **題目描述**：

思路

參考spfa算法，将節點增加或減少的值作為路徑長度，我們要做的是找到每個點到起點的最大路徑。在之前的Spfa算法中，我們是要尋找最短路徑，即 dist[u] + w[u][v] < dist[v] 則更新dist[v]。在此題中，我們需要尋找最長的那條路徑；即 dist[u] + w[u][v] > dist[v]，則需要更新dist[v]。在更新的過程中，若更新的某個點的最大路徑為負數，說明不能到達此房間，不要入隊。若最後不能到達目标點或者目标點的最大路徑為負，則判斷為No

注意：

在之前的最短路問題中，我們遇到負權值回路時，則其沒有最短路（可以一直在負權值回路中繞圈子）。在此題中，我們類比，當最長路可以不斷增加時，即存在正權值回路時，我們可以在這個圈子中一直繞。是以若有正環，說明可在此無限增加體力，可直接判斷為Yes。

代碼

#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;
}