競技プログラミング ベルマンフォード編 [備忘録]

はじめに

　制限時間内に問題を解く競技プログラミングにおいて、アルゴリズムを調べるために本を読み文字を打ち込むことはとてもめんどくさいと感じたため、ここにMain関数で呼び出して使える形で残しておくことでAtCoderでやるときにコピペで使えるようにしています。

ベルマンフォード法特徴

O(V*E)

プログラム上、入力が有向グラフ形式になっている。

無向グラフを表すには逆向きのものも辺として入力させればよい。

d[a]で終点をaとした最短経路のコストを入れている。

負の閉路があるときはNEGATIVE CYCLEと表示される。

ソースコード

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;
#define MV 100000
#define INF 1e9

struct edge{int to,cost; };
vector <edge> G[MV];

int V,E;
int d[MV+1];//最短径路を格納

bool bellmanford(int s){
  fill(d,d+MV,INF);
  d[s] = 0;
  int c = 0;
  bool upd = false;
  while(true){
    upd = false;
    for(int i = 0;i < V;i++){
      for(int j = 0;j < G[i].size();j++){
	edge e = G[i][j];
	if(d[i] != INF && d[e.to] > d[i] + e.cost){
	  d[e.to] = d[i] + e.cost;
	  upd = true;
	}
      }
    }
    if(!upd)
      break;
    if(c == V-1)
      return true;//負の閉路の判定
    c++;
  }
  return false;
}

int main(){
  d[MV] = INF+10;
  int first;
  bool flag;
  cin >> V >> E >> first;
  for(int i = 0;i < E;i++){
    int f,t;
    edge e;
    cin >> f >> e.to >> e.cost;
    G[f].push_back(e);
    /*
      G[f]にはfからでてる辺が格納されている。
     */
    t = e.to;
    
    //e.to = f;
    //G[t].push_back(e);
  }

  
  flag = bellmanford(first);
  if(flag == true)
    cout << "NEGATIVE CYCLE" << endl;
  else{
    for(int i = 0;i < V;i++){
      if(d[i] == INF){
	cout << "INF" << endl;
      }
      else{
	cout << d[i] << endl;
      }
    }
  }
  
}