题目链接:https://www.acwing.com/problem/content/description/854/
时/空限制：1s / 64MB

题目描述

给定一个n个点m条边的有向图，图中可能存在重边和自环， 边权可能为负数。

请你判断图中是否存在负权回路。

输入格式

第一行包含整数n和m。

接下来m行每行包含三个整数x，y，z，表示点x和点y之间存在一条有向边，边长为z。

输出格式

如果图中存在负权回路，则输出“Yes”，否则输出“No”。

数据范围

1≤n≤2000,
1≤m≤10000,
图中涉及边长绝对值均不超过10000。

输入样例

3 3
1 2 -1
2 3 4
3 1 -4

输出样例

Yes

解题思路

题意:判断图中是否存在负权回路。
思路:如果某条最短路径上有n个点(除了自己)，那么加上自己之后一共有n+1个点，那么一定有两个点相同，所以存在环。

Accepted Code:

/* 
 * @Author: lzyws739307453 
 * @Language: C++ 
 */
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2005;
const int MAXM = 10005;
const int inf = 0x3f3f3f3f;
bool vis[MAXN];
int f[MAXN], dis[MAXN], inq[MAXN], Adj;
struct AddTab {
    int u, v, w;
    AddTab() {}
    AddTab(int u, int v, int w) : u(u), v(v), w(w) {}
}e[MAXM];
void Add_Adj(int u, int v, int w) {
    e[++Adj] = AddTab(f[u], v, w);
    f[u] = Adj;
}
bool Spfa(int s, int n) {
    queue <int> Q;
    for (int i = 1; i <= n; i++) {
        Q.push(i);
        vis[i] = true;
    }
    while (!Q.empty()) {
        int u = Q.front();
        Q.pop();
        vis[u] = false;
        for (int i = f[u]; ~i; i = e[i].u) {
            int v = e[i].v;
            if (dis[v] > dis[u] + e[i].w) {
                dis[v] = dis[u] + e[i].w;
                if (++inq[v] >= n)//如果从1号点到x的最短路中包含至少n个点(不包括自己)，则说明存在环
                    return true;
                if (!vis[v]) {
                    Q.push(v);
                    vis[v] = true;
                }
            }
        }
    }
    return false;
}
int main() {
    int n, m;
    Adj = 0;
    memset(f, -1, sizeof(f));
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        Add_Adj(u, v, w);
    }
    if (Spfa(1, n))
        printf("Yes\n");
    else printf("No\n");
    return 0;
}