INF = 1000000000000000 n = gets.to_i stay = Array.new(n) n.times{ |i| stay[i] = gets.to_i } m = gets.to_i dist = Array.new(n) dp = Array.new(n) n.times{|i| dist[i] = Array.new(n, INF) dp[i] = Array.new(n, INF) } m.times{|i| a, b, c = gets.strip.split.map{|e| e.to_i} dist[a][b] = c dist[b][a] = c } # 初期化 for i in (0...n) for j in (0...n) if i == j dp[i][j] = 0 else dp[i][j] = dist[i][j] end end end # 2地点間の最短経路(ワーシャルフロイド) for k in (0...n) for i in (0...n) for j in (0...n) dp[i][j] = [dp[i][j], dp[i][k] + dp[k][j]].min end end end