結果

問題 No.748 yuki国のお財布事情
ユーザー ikd
提出日時 2018-07-18 00:51:30
言語 Ruby
(3.4.1)
結果
AC  
実行時間 762 ms / 2,000 ms
コード長 736 bytes
コンパイル時間 41 ms
コンパイル使用メモリ 7,296 KB
実行使用メモリ 22,144 KB
最終ジャッジ日時 2024-07-04 19:10:58
合計ジャッジ時間 9,421 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff # 

n, m, k = gets.split.map(&:to_i)

Edge = Struct.new("Edge", :u, :v, :cost)
edges = []
m.times do
  a, b, c = gets.split.map(&:to_i)
  edges.push(Edge.new(a - 1, b - 1, c))
end

class UnionFind
  def initialize(n)
    @par = (0...n).to_a
  end

  def find(i)
    @par[i] == i ? @par[i] : @par[i] = find(@par[i])
  end

  def unite(i, j)
    @par[find(i)] = find(j)
  end

  def same(i, j)
    find(i) == find(j)
  end
end

sum = 0
uf = UnionFind.new(n)
k.times do
  i = gets.chomp.to_i
  i -= 1
  uf.unite(edges[i].u, edges[i].v)
  sum += edges[i].cost
end
edges.sort { |a, b| a.cost <=> b.cost }.each do |e|
  unless uf.same(e.u, e.v)
    uf.unite(e.u, e.v)
    sum += e.cost
  end
end

puts edges.reduce(0) { |r, e| r + e.cost } - sum
0