結果

問題 No.95 Alice and Graph
ユーザー TANIGUCHI KousukeTANIGUCHI Kousuke
提出日時 2015-11-17 14:06:37
言語 Ruby
(3.3.0)
結果
TLE  
実行時間 -
コード長 1,376 bytes
コンパイル時間 128 ms
コンパイル使用メモリ 7,424 KB
実行使用メモリ 18,944 KB
最終ジャッジ日時 2024-09-13 15:58:08
合計ジャッジ時間 12,456 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
testcase_01 -- -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff # 

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, max_cost)
    s = (1 << n.size)
    dp = s.times.map { Array.new(n.size, INF) }
    q = []
    n.each_with_index do |v, i|
        used = 1 << i
        cost = G[v][0]
        q.push([used, i, cost])
    end
    until q.empty?
        used, pos, cost = q.shift
        u = n[pos]
        if cost < dp[used][pos]
            dp[used][pos] = cost
            n.each_with_index do |v,i|
                mask = 1 << i
                ncost = cost + G[v][u]
                if mask & used == 0 && ncost <= max_cost
                    q.unshift([used | mask, i, ncost ])
                end
            end
        end
    end
    dp[s - 1].min <= max_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

used = []
V.each do |v|
    if cover_all?(used.dup << v, k)
        used << v
    end
end
puts used.map{|v|  (1 << v) - 1 }.inject(0, &:+)
0