結果

問題 No.95 Alice and Graph
コンテスト
ユーザー TANIGUCHI Kousuke
提出日時 2015-11-10 00:38:53
言語 Ruby
(3.4.1)
結果
TLE  
実行時間 -
コード長 1,285 bytes
コンパイル時間 44 ms
コンパイル使用メモリ 7,552 KB
実行使用メモリ 22,172 KB
最終ジャッジ日時 2024-09-13 14:17:39
合計ジャッジ時間 12,653 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 13
権限があれば一括ダウンロードができます
コンパイルメッセージ
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
    dp = s.times.map { Array.new(n.size, INF) }
    dp[1][0] = 0
    s.times do |bit|
        n.each_with_index do |u,i|
            mask = 1 << i
            if mask & bit > 0
                q = dp[mask ^ bit].each_with_index.map {|used, j|
                    if ((mask ^ bit) & (1 << j)) > 0  
                        v = n[j]
                        used + G[u][v]
                    else
                        INF
                    end
                }.min
                if q <= dp[bit][i]
                    dp[bit][i] = q
                end
            end
        end
    end
    dp[s - 1].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
visited = [0]
V.each do |v|
    if cover_all?(visited.dup << v, k)
        visited << v
    end
end
puts visited.inject(0){|s,v| s - 1 + (1 << v) }
0