本文共 1549 字，大约阅读时间需要 5 分钟。

题意

问是否存在负环

AC

因为Dijkstra不能处理带有负边权的图，可以用spfa 和 BellmenFord

• spfa

using namespace std;int inf = 0x3f3f3f3f;struct ac{    int v, c;};int dis[N], cnt[N];bool vis[N];vector
   
     g[N];bool spfa(int start , int n) {    mem(cnt, 0);    mem(dis, inf);    mem(vis, false);    dis[start] = 0;    queue
    
      que;    // 将源点入队    que.push(start);    vis[start] = true;    cnt[start] = 1;    while (!que.empty()) {        int u = que.front();        que.pop();        vis[u] = false;        for (int i = 0; i < g[u].size(); ++i) {            int v = g[u][i].v;            int c = g[u][i].c;            if (dis[v] > dis[u] + c) {                dis[v] = dis[u] + c;                // 更新的点是否已经入队                if (vis[v] == false) {                    vis[v] = true;                    que.push(v);                    // 入队大于 n 次，存在负环                    if (++cnt[v] > n)   return true;                }            }        }    }    return false;}int main(){    freopen("in.txt", "r", stdin);    int n, m, w;    int t;    cin >> t;    while (t--) {        cin >> n >> m >> w;        for (int i = 0; i < m; ++i) {            int u, v, c;            cin >> u >> v >> c;            g[u].push_back((ac){v, c});            g[v].push_back((ac){u, c});        }        for (int i = 0; i < w; ++i) {            int u, v, c;            cin >> u >> v >> c;            g[u].push_back((ac){v, -c});        }        if (spfa(1, n)) cout << "YES\n";        else    cout << "NO\n";        for (int i = 0; i <= n; ++i) {            g[i].clear();        }    }    return 0;}
    
   

转载地址：http://ikprf.baihongyu.com/