verify/graph/floyd_warshall.test.cr

• View this file on GitHub
• Last update: 2024-07-28 06:26:08+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_C

Depends on

• src/nglib/graph/floyd_warshall.cr

Code

# verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_C

require "../../src/nglib/graph/floyd_warshall.cr"
require "big"

n, m = read_line.split.map &.to_i64
graph = NgLib::FloydWarshallGraph(BigInt).new(n)
m.times do
  u, v, w = read_line.split.map &.to_i64
  graph.add_edge(u, v, BigInt.new(w), directed: true)
end

d = graph.shortest_path
if n.times.any? { |i| (d[i][i] || Int64::MAX) < 0 }
  puts "NEGATIVE CYCLE"
else
  n.times do |i|
    puts d[i].map { |elem| elem || "INF" }.join ' '
  end
end

# verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_C

# require "../../src/nglib/graph/floyd_warshall.cr"
module NgLib
  # ワーシャル・フロイド法の実装です。
  #
  # （負を含む）重み付きグラフに対して、
  # 全点対最短経路長が $O(V^3)$ で求まります。
  class FloydWarshallGraph(T)
    getter size : Int32
    getter mat : Array(Array(T?))

    # $n$ 頂点 $0$ 辺のグラフを作ります。
    #
    # ```
    # n = 10
    # NgLib::FloydWarshallGraph(Int64).new(n)
    # ```
    def initialize(n : Int)
      @size = n.to_i32
      @mat = Array.new(n) { Array.new(n) { nil.as(T?) } }
      @size.times do |i|
        @mat[i][i] = T.zero
      end
    end

    # 隣接行列に従ってグラフを作ります。
    #
    # `nil` は辺が存在しないことを表します。
    # 無限大の重みを持つ辺と捉えても良いです。
    #
    # ```
    # mat = [[0, 3, 1], [-2, 0, 4], [nil, nil, 0]]
    # NgLib::FloydWarshallGraph(Int32).new(mat)
    # ```
    def initialize(@mat : Array(Array(T?)))
      @size = @mat.size
      @size.times do |i|
        @mat[i][i] = T.zero
      end
    end

    # :ditto:
    def initialize(matrix : Array(Array(T?) | Array(T)))
      @mat = matrix.map { |line| line.map { |v| v.as(T?) } }
      @size = @mat.size
      @size.times do |i|
        @mat[i][i] = T.zero
      end
    end

    # 重みが $w$ の辺 $(u, v)$ を追加します。
    #
    # `directed` が `true` である場合、有向辺として追加します。
    #
    # ```
    # n, m = read_line.split.map &.to_i
    # graph = NgLib::FloydWarshallGraph.new(n)
    # m.times do
    #   u, v, w = read_line.split.map &.to_i64
    #   u -= 1; v -= 1 # 0-index
    #   graph.add_edge(u, v, w, directed: true)
    # end
    # ```
    def add_edge(u : Int, v : Int, w : T, directed : Bool = true)
      uv = @mat[u][v]
      if uv.nil?
        @mat[u][v] = w
      else
        @mat[u][v] = {uv, w}.min
      end

      unless directed
        vu = @mat[v][u]
        if vu.nil?
          @mat[v][u] = w
        else
          @mat[v][u] = {vu, w}.min
        end
      end
    end

    # 全点対最短経路長を返します。
    #
    # どのような経路を辿っても到達できない場合は `nil` が格納されます。
    #
    # ```
    # mat = [[0, 3, 1], [-2, 0, 4], [nil, nil, 0]]
    # graph = NgLib::FloydWarshallGraph.new(mat)
    # d = graph.shortest_path # => [[0, 3, 1], [-2, 0, -1], [nil, nil, 0]]
    # d[0][1]                 # => 3  (i から j への最短経路長)
    # ```
    def shortest_path
      dist = @mat.clone
      @size.times do |via|
        @size.times do |from|
          @size.times do |dest|
            d1 = dist[from][via]
            d2 = dist[via][dest]
            next if d1.nil?
            next if d2.nil?
            d = dist[from][dest]
            if d.nil? || d > d1 + d2
              dist[from][dest] = d1 + d2
            end
          end
        end
      end
      dist
    end
  end
end
require "big"

n, m = read_line.split.map &.to_i64
graph = NgLib::FloydWarshallGraph(BigInt).new(n)
m.times do
  u, v, w = read_line.split.map &.to_i64
  graph.add_edge(u, v, BigInt.new(w), directed: true)
end

d = graph.shortest_path
if n.times.any? { |i| (d[i][i] || Int64::MAX) < 0 }
  puts "NEGATIVE CYCLE"
else
  n.times do |i|
    puts d[i].map { |elem| elem || "INF" }.join ' '
  end
end

Back to top page