Submission #1272642

---

Source Code Expand

N, M, *rest = $stdin.read.split.map(&:to_i)

dist = Array.new(N){ Array.new(N, Float::INFINITY) }
N.times{|i| dist[i][i] = 0}

rest.each_slice(3) do |a, b, t|
  dist[a-1][b-1] = t
  dist[b-1][a-1] = t
end

N.times do |k|
  N.times do |i|
    N.times do |j|
      newd = dist[i][k] + dist[k][j]
      dist[i][j] = newd if newd < dist[i][j]
    end
  end
end

p dist.map(&:max).min

Submission Info

Judge Result