結果

問題 No.95 Alice and Graph
ユーザー TANIGUCHI KousukeTANIGUCHI Kousuke
提出日時 2015-11-10 14:59:58
言語 Ruby
(3.3.0)
結果
WA  
実行時間 -
コード長 1,112 bytes
コンパイル時間 60 ms
コンパイル使用メモリ 11,240 KB
実行使用メモリ 31,452 KB
最終ジャッジ日時 2023-10-11 15:31:18
合計ジャッジ時間 11,657 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 RE -
testcase_02 RE -
testcase_03 AC 156 ms
31,436 KB
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 RE -
testcase_08 AC 107 ms
17,428 KB
testcase_09 AC 82 ms
15,044 KB
testcase_10 AC 83 ms
15,100 KB
testcase_11 AC 114 ms
17,408 KB
testcase_12 AC 107 ms
17,004 KB
testcase_13 AC 1,254 ms
30,072 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff # 

# Here your code !
INF = 1 << 10

def warshal(n,e)
    g = n.times.map {|i| n.times.map {|j| i == j ? 0 : INF} }
    e.each do |u,v|
        g[u][v] = g[v][u] = 1
    end
    n.times do |i|
        n.times do |j|
            g[j][i] = g[i][j] = n.times.map {|k| g[i][k] + g[k][j] }.min
        end
    end
    g
end

def cover_all?(n, cost)
    s = 1 << (n.size - 1)
    t = (1 << n.size) - 1
    (s .. t).each do |bit|
        n.each_with_index do |u,j|
            mask = (1 << j)
            if mask & bit > 0
                DP[bit][j] = n.each_with_index.map {|v, i|
                    DP[mask ^ bit][i] + G[u][v]
                }.min || INF
            end
        end
    end
    DP[t].min <= cost
end

n,m,k = gets.split.map(&:to_i)
e = m.times.map do
    gets.split.map(&:to_i).map{|v| v - 1} 
end

G = warshal(n, e)

V = n.times.to_a.drop(1).reverse
V.select! {|v| G[0][v] <= k }

visited = [0]

DP = (1 << (k+1)).times.map { Array.new(k+1,INF) }
DP[1][0] = 0

V.all? do |v|
    if cover_all?(visited.dup << v, k + 1)
        visited << v
    end
end

puts visited.inject(0){|s,v| s - 1 + (1 << v) }
0