spfa

KellyFrog · 2019-11-24 19:15:52 · 题解

\text{spfa}

--队列优化的\text{bellman-ford}算法

\text{spfa}判负环（咕咕咕咕）

code:\text{spfa}模板

#include <iostream>
#include <fstream>
#include <queue>
#include <cstdlib>

using namespace std;

const int MAXN = 5e5 + 5;

int head[MAXN], next[MAXN], to[MAXN], weight[MAXN];
int tot = 0;

int n, m, s;
int dis[MAXN], vis[MAXN];
bool inQueue[MAXN];
queue<int> q;

void AddEdge(int u, int v, int w) {
  next[++tot] = head[u];
  to[tot] = v;
  weight[tot] = w;
  head[u] = tot;
}

bool Relax(int u, int v, int w) {
  if(dis[v] > dis[u] + w) {
    dis[v] = dis[u] + w;
    return true;
  }
  return false;
}

void Error() {
  cout << "negetive loop!" << endl;
  exit(0);
}

void Spfa(int start) {
  for(int i = 0; i < MAXN; i++) {
    dis[i] = 2147483647;
  }
  q.push(start);
  inQueue[start] = true;
  dis[start] = 0;
  vis[start] = 1;
  while(!q.empty()) {
    int u = q.front();
    q.pop();
    vis[u]++;
    inQueue[u] = false;
    if(vis[u] > n) { //判负环 
      Error();
    }
    for(int i = head[u]; i; i = next[i]) {
      int v = to[i];
      int w = weight[i];
      if(Relax(u, v, w) && !inQueue[v]) {
    q.push(v);
        inQueue[v] = false;
      }
    }
  }
}

int main() {
  ifstream inFile("spfa.in");
  cin >> n >> m >> s;
  for(int i = 0; i < m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    AddEdge(u, v, w);
  }
  Spfa(s);
  for(int i = 1; i < n + 1; i++) {
    cout << dis[i] << ' ';
  }
  cout << endl;
  return 0;
}