Submission #14152776

---

Source Code Expand

def min(a,b); a < b ? a : b; end
INF = 10 ** 7
N,M = gets.split.map(&:to_i)
G = Array.new(N + 1){ [] }
M.times do
  u,v = gets.split.map(&:to_i)
  G[u] << v
  G[v] << u
end
S,K = 2.times.map{ gets.to_i }
T = gets.split.map(&:to_i)

def shortest_path(s)
  used = Array.new(N + 1)
  dist = Array.new(N + 1, INF)
  q = [s]
  used[s] = true
  dist[s] = 0
  
  until q.empty?
    u = q.shift
    d = dist[u]
    
    G[u].each do |v|
      next if used[v]
      
      used[v] = true
      dist[v] = d + 1
      q << v
    end
  end
  dist
end


D = T.map{|t| shortest_path(t) }

init = shortest_path(S)
dp = Array.new(K){ Array.new(1 << K, Float::INFINITY) }

T.each_with_index do |t,i|
  dp[i][1 << i] = init[t]
end

(1 << K).times do |visited|
  T.each_with_index do |from, i|
    next if dp[i][visited] > INF
    T.each_with_index do |to,j|
      dp[j][visited | 1 << j] = min(dp[i][visited] + D[i][to], dp[j][visited | 1 << j])
    end
  end
end
puts K.times.map{|i| dp[i][-1] }.min

Submission Info

Judge Result