結果

問題 No.748 yuki国のお財布事情
ユーザー ikdikd
提出日時 2018-07-18 00:51:30
言語 Ruby
(3.3.0)
結果
AC  
実行時間 744 ms / 2,000 ms
コード長 736 bytes
コンパイル時間 276 ms
コンパイル使用メモリ 11,328 KB
実行使用メモリ 26,116 KB
最終ジャッジ日時 2023-09-18 02:22:21
合計ジャッジ時間 9,641 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 81 ms
15,028 KB
testcase_01 AC 81 ms
15,068 KB
testcase_02 AC 81 ms
15,028 KB
testcase_03 AC 81 ms
15,068 KB
testcase_04 AC 79 ms
15,288 KB
testcase_05 AC 79 ms
15,284 KB
testcase_06 AC 80 ms
15,156 KB
testcase_07 AC 82 ms
15,076 KB
testcase_08 AC 80 ms
15,072 KB
testcase_09 AC 80 ms
15,300 KB
testcase_10 AC 81 ms
15,100 KB
testcase_11 AC 79 ms
15,072 KB
testcase_12 AC 80 ms
15,072 KB
testcase_13 AC 141 ms
16,320 KB
testcase_14 AC 189 ms
16,596 KB
testcase_15 AC 157 ms
16,432 KB
testcase_16 AC 304 ms
18,412 KB
testcase_17 AC 581 ms
22,996 KB
testcase_18 AC 675 ms
25,616 KB
testcase_19 AC 744 ms
26,116 KB
testcase_20 AC 658 ms
23,324 KB
testcase_21 AC 616 ms
23,432 KB
testcase_22 AC 79 ms
15,140 KB
testcase_23 AC 79 ms
15,252 KB
testcase_24 AC 79 ms
15,096 KB
testcase_25 AC 544 ms
22,880 KB
testcase_26 AC 611 ms
23,796 KB
testcase_27 AC 586 ms
23,780 KB
testcase_28 AC 502 ms
22,280 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