結果

問題 No.95 Alice and Graph
コンテスト
ユーザー TANIGUCHI Kousuke
提出日時 2015-11-11 13:25:08
言語 Ruby
(4.0.0)
結果
TLE  
実行時間 -
コード長 1,650 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 188 ms
コンパイル使用メモリ 7,552 KB
実行使用メモリ 24,480 KB
最終ジャッジ日時 2024-09-13 14:24:58
合計ジャッジ時間 12,590 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 13
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff #
raw source code 

# Here your code !
def dot(n,e)
    <<-EOT
graph {
    node #{ n.times.map{|i| i + 1}.join(' ')};
    #{ e.map{|(u,v)| "#{u+1} -- #{v+1};"}.join("\n") }
}
    EOT
end

INF = 1 << 20
def warshal(n,e)
    g = n.times.map { Array.new(n,INF) }
    n.times do |u|
        g[u][u] = 0
    end
    e.each do |(u,v)|
        g[u][v] = g[v][u] = 1
    end
    n.times do |i|
        n.times do |j|
            n.times do |k|
                if g[i][k] + g[k][j] < g[i][j] 
                    g[j][i] = g[i][j] = g[i][k] + g[k][j]
                end
            end
        end
    end
    g
end

def cover_all?(n, cost)
    s = 1 << (n.size - 1)
    t = (1 << n.size) - 1
    
    (s..t).each do |bit|
        DP[bit].fill(INF)
    end
    DP[1 << (n.size - 1)][n.size - 1] = G[0][n.last]
    (s..t).each do |bit|
        n.each_with_index do |v,i|
            to = 1 << i
            if bit & to > 0
                prev = bit ^ to
                n.each_with_index do |u,j|
                    from = 1 << j
                    if prev & from > 0
                        uv = DP[prev][j] + G[u][v]
                        if uv < DP[bit][i]
                            DP[bit][i] = uv
                        end
                    end
                end
            end
        end
    end
    DP[t].find {|c| c <= cost}
end


n,m,k = gets.split.map(&:to_i)
e = m.times.map { gets.split.map(&:to_i).map{|v| v - 1} }
G = warshal(n,e)
V = n.times.to_a.drop(1).reverse
DP = (1 << k).times.map { Array.new(k,INF) }
used = []
V.each do |v|
    if cover_all?(used.dup << v, k)
        used << v
    end
end
puts used.map{|v|  2 ** v - 1 }.inject(0, &:+)
0