結果
問題 | No.748 yuki国のお財布事情 |
ユーザー |
![]() |
提出日時 | 2018-10-19 22:18:21 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 507 ms / 2,000 ms |
コード長 | 1,062 bytes |
コンパイル時間 | 100 ms |
コンパイル使用メモリ | 12,672 KB |
実行使用メモリ | 32,344 KB |
最終ジャッジ日時 | 2024-11-18 21:08:27 |
合計ジャッジ時間 | 5,950 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
def kruskal(v_count: int, edges: list) -> int: """ :param v_count: 頂点数 :param edges: [(weight, from, to), ... ] """ from itertools import islice tree = [-1]*v_count def get_root(x) -> int: if tree[x] < 0: return x tree[x] = get_root(tree[x]) return tree[x] def unite(a) -> bool: x, y = get_root(a[1]), get_root(a[2]) if x != y: big, small = (x, y) if tree[x] < tree[y] else (y, x) tree[big] += tree[small] tree[small] = big return x != y cost = 0 for w, _s, _t in islice(filter(unite, sorted(edges)), v_count-1): cost += w return cost if __name__ == "__main__": import sys N, M, K = map(int, input().split()) edges = [[c, a-1, b-1] for _ in [0]*M for a, b, c in (map(int, sys.stdin.readline().split()),)] total = sum(v[0] for v in edges) cost = 0 for e in map(int, sys.stdin): cost += edges[e-1][0] edges[e-1][0] = 0 print(total - (kruskal(N, edges) + cost))