Submission #73394290

---

Source Code Expand

n,m = gets.split.map(&:to_i)
s,t = gets.split.map(&:to_i)
if m != 0
  p = gets.split.map(&:to_i)
else
  p = []
end
p.unshift(s)
p << t
m += 2
dist = Array.new(m){Array.new(m,-1)}
m.times do |i|
  m.times do |j|
    next if i == j
    ir = (p[i]-1)/n
    ic = (p[i]-1)%n
    jr = (p[j]-1)/n
    jc = (p[j]-1)%n
    dist[i][j] = (ir-jr).abs + (ic-jc).abs
  end
end

bit = 1<<m
dp = Array.new(bit){Array.new(m,10**18)}
#初期化
dp[1][0] = 0
i = 0
while i < bit
  zumi,mada = m.times.partition{|v| i[v] == 1}
  zumi.each do |j|
    gj = dist[j]
    dpij = dp[i][j]
    mada.each do |k|
      x = dpij + gj[k]
      y = i|(1<<k)
      dp[y][k] = x if dp[y][k] > x
    end
  end
  i += 1
end

puts dp[bit-1][m-1]

Submission Info

Judge Result