spfa

59percent · 2019-10-27 15:45:33 · 个人记录

void spfa(int v0) {
  memset(d, 0x3f, sizeof(d));
  memset(vis, false, sizeof(vis));
  d[v0] = 0;
  vis[v0] = true;
  q.push(v0);
  while(!q.empty()) {
    int x = q.front();
    q.pop();
    vis[x] = false;
    for(int i=0; i<g[x].size(); i++) {
      int y=g[x][i].y, w=g[x][i].w;
      if(d[x]+w < d[y]) {
        d[y] = d[x]+w;
        if(vis[y]) continue;
        vis[y] = true;
        q.push(y);
      }
    }
  }
}

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

struct Edge {
  int y,w;
};

const int inf = 0x3f3f3f3f;
const int N=1005;
int n,m,s, d[N], cnt[N];
vector<Edge> g[N];
bool vis[N];
queue<int> q;

bool spfa(int v0) {
  memset(d, 0x3f, sizeof(d));
  memset(vis, false, sizeof(vis));//是否已入队，和bfs一样

  d[v0] = 0;
  vis[v0] = true;
  q.push(v0);
  while(!q.empty()) {
    //1. 出队
    int x = q.front();
    q.pop();
    //2. 可重复入队
    vis[x] = false;
    //3. 松弛后面的
    for(int i=0; i<g[x].size(); i++) {
      int y=g[x][i].y, w=g[x][i].w;
      if(d[x]+w < d[y]) {
        d[y] = d[x]+w;
        if(vis[y]) continue;
        vis[y] = true;
        q.push(y);
      }
    }
  }
  return true;
}

int main() {
  cin>>n>>m>>s;
  for(int i=1; i<=m; i++) {
    int x,y,w;
    cin>>x>>y>>w;
    Edge e = (Edge){y, w};
    g[x].push_back(e);
  }

  bool flag = spfa(s);

  if(!flag) {
    cout<<"有负环"<<endl;
    return 0;
  }

  for(int i=1; i<=n; i++)
    cout<<(d[i]==inf?-1:d[i])<<" ";
  return 0;
}

#include <iostream>
using namespace std;

const int inf=0x3f3f3f3f;
const int N=20;
int n, m, k;
int d[N][N];//邻接矩阵

int main() {
  cin>>n>>m>>k;

  //1. 初始化
  for(int i=1; i<=n; i++)
    for(int j=1; j<=n; j++)
      d[i][j] = i==j? 0: inf;

  //2、输入\更新
  for(int i=1; i<=m; i++) {
    int x, y, w;
    cin>>x>>y>>w;
    d[x][y] = d[y][x] = w;
  }

  //3. 持续松弛：经过点k的路径，有前面的点i，有后面的点j
  for(int k=1; k<=n; k++)//k在前面
    for(int i=1; i<=n; i++)
      for(int j=1; j<=n; j++)
        if(d[i][k]+d[k][j] < d[i][j])
          d[i][j] = d[i][k]+d[k][j];

  for(int i=1; i<=k; i++) {
    int x, y;
    cin>>x>>y;
    cout<<d[x][y]<<endl;
  }
  return 0;
}

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

struct Edge {
  int y,w;
};

const int inf = 0x3f3f3f3f;
const int N=100005;
int n,m,s, d[N], cnt[N];
vector<Edge> g[N];
bool vis[N];
queue<int> q;

bool spfa(int v0) {
  memset(d, 0x3f, sizeof(d));
  memset(vis, false, sizeof(vis));
  d[v0] = 0;
  vis[v0] = true;
  cnt[v0] = 1;
  q.push(v0);
  while(!q.empty()) {
    int x = q.front();
    q.pop();
    vis[x] = false;
    for(int i=0; i<g[x].size(); i++) {
      int y=g[x][i].y, w=g[x][i].w;
      if(d[x]+w < d[y]) {
        d[y] = d[x]+w;
        cnt[y] = cnt[x] + 1;
        if(cnt[y]>n) {
          return false;
        }
        if(vis[y]) continue;
        vis[y] = true;
        q.push(y);
      }
    }
  }
  return true;
}

int main() {
  cin>>n>>m>>s;
  for(int i=1; i<=m; i++) {
    int x,y,w;
    cin>>x>>y>>w;
    Edge e = {y, w};
    g[x].push_back(e);
  }

  bool flag = spfa(s);

  if(!flag) {
    cout<<"有负环"<<endl;
    return 0;
  }

  for(int i=1; i<=n; i++)
    cout<<(d[i]==inf?2147483647:d[i])<<" ";
  return 0;
}