ベルマン–フォード法

procedure BellmanFord(list vertices, list edges, vertex source)
   // この実装では、グラフを頂点のリストと辺のリストで表す。
   // そして、各頂点の distance と predecessor 属性が
   // 最短経路を格納するよう変更していく。

   // Step 1: グラフの初期化
   for each vertex v in vertices:
       if v is source then v.distance := 0
       else v.distance := infinity
       v.predecessor := null
   
   // Step 2: 辺の緩和を反復
   for i from 1 to size(vertices) - 1:       
       for each edge uv in edges: // uv は u から v に向かう辺
           u := uv.source
           v := uv.destination             
           if v.distance > u.distance + uv.weight:
               v.distance := u.distance + uv.weight
               v.predecessor := u

   // Step 3: 負の重みの閉路がないかチェック
   for each edge uv in edges:
       u := uv.source
       v := uv.destination
       if u.distance + uv.weight < v.distance:
           error "Graph contains a negative-weight cycle"

INF  = Float::INFINITY
Edge = Struct.new(:from, :to, :cost)

class Graph
  attr :edges, :V, :E, :d
  def initialize(v,e)
    @V = v
    @E = e
    @edges = []
    @d = []
  end

  def add_graph_edge(u, v, w)
    @edges << Edge.new(u,v,w)
  end

  def bellman_ford(source=0)
    @d = Array.new(@V,INF)
    @d[source] = 0

    for count in [email protected]
      for i in [email protected]
        v = edges[i].to
        u = edges[i].from
        c = edges[i].cost

        if @d[u] + c < @d[v]
          @d[v] = @d[u] + c
          return false if (count == @V-1)
        end
      end
    end
    true
  end
end

INF  = Float::INFINITY
Edge = Struct.new(:from, :to, :cost)

class Graph
  attr :edges, :V, :E, :d
  def initialize(v,e)
    @V = v
    @E = e
    @edges = []
    @d = []
  end

  def add_graph_edge(u, v, w)
    @edges << Edge.new(u,v,w)
  end

  def bellman_ford(source=0)
    @d = Array.new(@V,INF)
    @d[source] = 0

    for count in [email protected]
      for i in [email protected]
        v = edges[i].to
        u = edges[i].from
        c = edges[i].cost
        #puts "from[#{u}] to[#{v}] cost=#{c},count=#{count}"
        if @d[u] + c < @d[v]
          @d[v] = @d[u] + c
          #p count
          #p v
          return false if (count == @V-1)
        end
      end
    end
    true
  end
end

lines = <<'EOS'
10 12 8
0 1 7
1 2 -3
2 3 3
3 0 -7
4 2 1
4 5 1
5 6 2
6 7 3
7 4 4
6 8 1
8 9 1
9 8 -7
EOS

#lines = $stdin.read
array = lines.split("\n")

V,E,R = array[0].split(" ").map(&:to_i)
graph = Graph.new(V,E)

array[1..E].each do |s|
  s,t,d = s.split(" ").map(&:to_i)
  graph.add_graph_edge(s,t,d)
end

if graph.bellman_ford(R)
  graph.d.each do |d|
    if d == INF
      puts "INF"
    else
      puts d
    end
  end
else
  puts "NEGATIVE CYCLE"
end