結果
問題 | No.1690 Power Grid |
ユーザー |
![]() |
提出日時 | 2021-09-24 22:43:45 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 556 ms / 3,000 ms |
コード長 | 2,682 bytes |
コンパイル時間 | 3,501 ms |
コンパイル使用メモリ | 88,104 KB |
実行使用メモリ | 62,420 KB |
最終ジャッジ日時 | 2024-07-05 11:03:26 |
合計ジャッジ時間 | 11,070 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 25 |
ソースコード
import java.util.ArrayList;import java.util.Collections;import java.util.List;import java.util.PriorityQueue;import java.util.Scanner;public class Main {public static void main(String[] args) throws Exception {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int m = sc.nextInt();int k = sc.nextInt();int[] a = new int[n];for (int i = 0; i < n; i++) {a[i] = sc.nextInt();}long inf = 1000000000000L;long[][] d = new long[n][n];for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (i != j) {d[i][j] = inf;}}}for (int i = 0; i < m; i++) {int x = sc.nextInt() - 1;int y = sc.nextInt() - 1;int z = sc.nextInt();d[x][y] = z;d[y][x] = z;}for (int p = 0; p < n; p++) {for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (d[i][p] != inf && d[p][j] != inf) {d[i][j] = Math.min(d[i][j], d[i][p] + d[p][j]);}}}}sc.close();List<Obj> list = new ArrayList<>();for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (i != j) {Obj o = new Obj();o.x = i;o.y = j;o.z = d[i][j];list.add(o);}}}Collections.sort(list, (o1, o2) -> Long.compare(o1.z, o2.z));long ans = Long.MAX_VALUE;int end = 1 << n;for (int i = 0; i < end; i++) {if (Integer.bitCount(i) != k) {continue;}PriorityQueue<Integer> que = new PriorityQueue<>();for (int j = 0; j < n; j++) {if ((i >> j & 1) == 1) {que.add(a[j]);}}long val = 0;for (int j = 0; j < k; j++) {val += que.poll();}UnionFind uf = new UnionFind(n);for (Obj o : list) {if ((i >> o.x & 1) == 1 && (i >> o.y & 1) == 1&& !uf.same(o.x, o.y)) {uf.union(o.x, o.y);val += o.z;}}ans = Math.min(ans, val);}System.out.println(ans);}static class Obj {int x, y;long z;}static class UnionFind {int[] parent, size;int num = 0; // 連結成分の数UnionFind(int n) {parent = new int[n];size = new int[n];num = n;for (int i = 0; i < n; i++) {parent[i] = i;size[i] = 1;}}void union(int x, int y) {int px = find(x);int py = find(y);if (px != py) {parent[px] = py;size[py] += size[px];num--;}}int find(int x) {if (parent[x] == x) {return x;}parent[x] = find(parent[x]);return parent[x];}/*** xとyが同一連結成分か*/boolean same(int x, int y) {return find(x) == find(y);}/*** xを含む連結成分のサイズ*/int size(int x) {return size[find(x)];}}}