結果
問題 | No.748 yuki国のお財布事情 |
ユーザー |
![]() |
提出日時 | 2018-10-20 00:23:38 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 818 ms / 2,000 ms |
コード長 | 989 bytes |
コンパイル時間 | 299 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 48,548 KB |
最終ジャッジ日時 | 2024-11-18 23:25:41 |
合計ジャッジ時間 | 9,228 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
N, M, K = map(int, input().split())Root = [n for n in range(N)]Root_num = [1 for n in range(N)]edges = [None for _ in range(M)]for m in range(M):a, b, c = map(int, input().split())edges[m] = (a-1, b-1, c)abs_edges = set(int(input())-1 for _ in range(K))sorted_edges = sorted([e for e in set(range(M)) - abs_edges], key=lambda x: edges[x][2])# 最小木T = {edges[e] for e in abs_edges}del_weight = 0def get_Root(c):if Root[c] == c:return celse:return get_Root(Root[c])def merge(a, b):root_a = get_Root(a)root_b = get_Root(b)if Root_num[root_a] < Root_num[root_b]:Root[root_a] = Root[root_b]Root_num[root_b] += Root_num[root_a]else:Root[root_b] = Root[root_a]Root_num[root_a] += Root_num[root_b]# union treefor e in abs_edges:a, b, c = edges[e]merge(a, b)for e in sorted_edges:# edge eを追加できるかどうかa, b, c = edges[e]if get_Root(a) == get_Root(b):del_weight += ccontinuemerge(a, b)print(del_weight)