結果

問題 No.1690 Power Grid
ユーザー ks2m
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

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];
}
/**
* xy
*/
boolean same(int x, int y) {
return find(x) == find(y);
}
/**
* x
*/
int size(int x) {
return size[find(x)];
}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0