結果

問題 No.748 yuki国のお財布事情
ユーザー ikdikd
提出日時 2018-07-18 00:51:30
言語 Ruby
(3.3.0)
結果
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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 85 ms
12,288 KB
testcase_01 AC 95 ms
12,160 KB
testcase_02 AC 89 ms
12,288 KB
testcase_03 AC 86 ms
12,032 KB
testcase_04 AC 85 ms
12,160 KB
testcase_05 AC 84 ms
12,160 KB
testcase_06 AC 84 ms
12,160 KB
testcase_07 AC 85 ms
12,032 KB
testcase_08 AC 84 ms
12,288 KB
testcase_09 AC 87 ms
12,160 KB
testcase_10 AC 87 ms
12,160 KB
testcase_11 AC 85 ms
12,160 KB
testcase_12 AC 85 ms
12,160 KB
testcase_13 AC 151 ms
13,312 KB
testcase_14 AC 207 ms
14,080 KB
testcase_15 AC 164 ms
13,568 KB
testcase_16 AC 318 ms
16,128 KB
testcase_17 AC 586 ms
20,736 KB
testcase_18 AC 697 ms
21,760 KB
testcase_19 AC 762 ms
21,888 KB
testcase_20 AC 690 ms
21,632 KB
testcase_21 AC 652 ms
21,760 KB
testcase_22 AC 86 ms
12,032 KB
testcase_23 AC 84 ms
12,032 KB
testcase_24 AC 86 ms
12,288 KB
testcase_25 AC 578 ms
20,608 KB
testcase_26 AC 612 ms
22,144 KB
testcase_27 AC 613 ms
21,632 KB
testcase_28 AC 514 ms
18,432 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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