Submission #351836

---

Source Code Expand

def calc(d,n)
  sum = 0
  n.times do |i|
    n.times do |j|
      sum += d[i][j] if d[i][j] < INF
    end
  end
  sum
end

n, m = gets.strip.split(' ').map(&:to_i)

INF = 999999.freeze
d = Array.new(n){ Array.new(n, INF) }
m.times do
  a, b, c = gets.strip.split(' ').map(&:to_i)
  d[a-1][b-1] = c
end


n.times do |i|
  n.times do |j|
    n.times do |k|
      d[i][j] = [d[i][j], d[i][k] + d[k][j]].min
    end
  end
end

kk = gets.strip.to_i
kk.times do
  a, b, c = gets.strip.split(' ').map(&:to_i)
  if d[a-1][b-1] > c
    d[a-1][b-1] = c
    n.times do |i|
      n.times do |j|
        n.times do |k|
          d[i][j] = [d[i][j], d[i][k] + d[k][j]].min
        end
      end
    end
  end
  puts calc(d, n)
end

Submission Info

Judge Result