Ruby で解く AtCoder ABC012 D Numo::NArray ワーシャル–フロイド法 - Qiita

はじめに AtCoder さん、ありがとうございます。 D - バスと避けられない運命 ワーシャル–フロイド法は、最短経路問題で利用されます。 Ruby Numo::NArray なし n, m = gets.split.map(&:to_i) ab = Array.new(n) { Array.new(n, 1000000000) } n.times do |i| ab[i][i] = 0 end m.times do a, b, t = gets.split.map(&:to_i) ab[a - 1][b - 1] = t ab[b - 1][a - 1] = t end n.times do |k| n.times do |i| n.times do |j| ab[i][j] = ab[i][k] + ab[k][j] if ab[i][j] > ab[i][k] + ab[k][j