Skip to content

Instantly share code, notes, and snippets.

@whatalnk
Created September 25, 2018 09:51
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save whatalnk/be0ad30b05990e419f0aa34e9d25752f to your computer and use it in GitHub Desktop.
Save whatalnk/be0ad30b05990e419f0aa34e9d25752f to your computer and use it in GitHub Desktop.
AtCoder ABC #079 D
h, w = gets.chomp.split(" ").map(&:to_i)
c = Array.new()
10.times do
c << gets.chomp.split(" ").map(&:to_i)
end
a = Array.new()
h.times do
a << gets.chomp.split(" ").map(&:to_i)
end
# dijkstra
INF = 10**6
n = 10
s = 1
d = Array.new(n, INF)
used = Array.new(n, false)
d[s] = 0
while true
v = -1
n.times do |u|
if !used[u] && (v == -1 || d[u] < d[v])
v = u
end
end
break if v == -1
used[v] = true
n.times do |u|
if d[u] > d[v] + c[u][v]
d[u] = d[v] + c[u][v]
end
end
end
ans = 0
a.each do |row|
row.each do |cell|
if cell < 0
next
else
ans += d[cell]
end
end
end
puts ans
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment