結果
問題 | No.748 yuki国のお財布事情 |
ユーザー |
![]() |
提出日時 | 2020-01-30 18:18:51 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 538 ms / 2,000 ms |
コード長 | 2,961 bytes |
コンパイル時間 | 2,455 ms |
コンパイル使用メモリ | 77,936 KB |
実行使用メモリ | 49,532 KB |
最終ジャッジ日時 | 2024-09-16 03:46:10 |
合計ジャッジ時間 | 9,743 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
import java.util.*;import java.io.*;public class Main {static int[] dp;public static void main(String[] args) throws Exception {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));String[] first = br.readLine().split(" ", 3);int n = Integer.parseInt(first[0]);int m = Integer.parseInt(first[1]);int k = Integer.parseInt(first[2]);Route[] routes = new Route[m];long total = 0;for (int i = 0; i < m; i++) {routes[i] = new Route(br.readLine());total += routes[i].cost;}UnionFindTree uft = new UnionFindTree(n);for (int i = 0; i < k; i++) {int idx = Integer.parseInt(br.readLine()) - 1;uft.unite(routes[idx]);total -= routes[idx].cost;routes[idx].cost = Integer.MAX_VALUE;}Arrays.sort(routes);for (int i = 0; i < m && !uft.isFull(); i++) {if (!uft.same(routes[i])) {total -= routes[i].cost;uft.unite(routes[i]);}}System.out.println(total);}static class UnionFindTree {int[] parents;int[] counts;public UnionFindTree(int size) {parents = new int[size];counts = new int[size];for (int i = 0; i < size; i++) {parents[i] = i;counts[i] = 1;}}public int find(int x) {if (parents[x] == x) {return x;} else {return parents[x] = find(parents[x]);}}public boolean same(int x, int y) {return find(x) == find(y);}public boolean same(Route r) {return same(r.left, r.right);}public void unite(int x, int y) {int xx = find(x);int yy = find(y);if (xx == yy) {return;} else if (xx > yy) {parents[xx] = yy;counts[yy] += parents[xx];} else {parents[yy] = xx;counts[xx] += parents[yy];}}public void unite(Route r) {unite(r.left, r.right);}public boolean isFull() {return counts[0] == counts.length;}}static class Route implements Comparable<Route> {int left;int right;int cost;public Route(String s) {String[] arr = s.split(" ", 3);left = Integer.parseInt(arr[0]) - 1;right = Integer.parseInt(arr[1]) - 1;cost = Integer.parseInt(arr[2]);}public int compareTo(Route another) {return cost - another.cost;}}}