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

• 判断是否存在负环
• 求带有负边权的最短路
  当某个点入队大于N次，一定存在负环。
• 其他
  一直纠结能否把判断一个点被更新N次作为判断依据
  临接表不行因为数据可能两个点之间有大于N条边，而且每条边是降序排列
  临接矩阵不知道行不行

模板

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

dfs判断负环

struct ac{
       int v, w;};int dis[maxn], vis[maxn], flag;vector
   
     g[maxn];void Spfa(int x) {
       vis[x] = 1;    for (int i = 0, v,w; i < (int)g[x].size(); ++i) {
           v = g[x][i].v;        w = g[x][i].w;        if (dis[v] <= dis[x] + w) continue;        if (vis[v]) {
               flag = 1;            return;        }        dis[v] = dis[x] + w;        Spfa(v);        if (flag) return;    }    vis[x] = 0;}int main() {
       flag = 0;    mem(dis, inf);    mem(vis, 0);    dis[1] = 0;    Spfa(1);    return 0;}
   

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