結果
問題 |
No.114 遠い未来
|
ユーザー |
|
提出日時 | 2025-09-04 15:57:28 |
言語 | D (dmd 2.109.1) |
結果 |
TLE
|
実行時間 | - |
コード長 | 3,732 bytes |
コンパイル時間 | 5,698 ms |
コンパイル使用メモリ | 241,480 KB |
実行使用メモリ | 13,684 KB |
最終ジャッジ日時 | 2025-09-04 15:57:41 |
合計ジャッジ時間 | 12,008 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | -- * 3 |
other | AC * 1 TLE * 1 -- * 23 |
ソースコード
module main; // https://kmjp.hatenablog.jp/entry/2014/12/29/0900 より import std; import core.bitop; // 多次元配列をある値で埋める void fill(A, T)(ref A a, T value) if (isArray!A) { alias E = ElementType!A; static if (isArray!E) { foreach (ref e; a) fill(e, value); } else { a[] = value; } } // aとbを比較してbの方が小さいならばaの値をbに更新する void chMin(T)(ref T a, in T b) { if (a > b) a = b; } /* UnionFind:素集合系管理の構造体(union by size) isSame(x, y): x と y が同じ集合にいるか。 計算量はならし O(α(n)) unite(x, y): x と y を同じ集合にする。計算量はならし O(α(n)) treeSize(x): x を含む集合の要素数。 */ struct UnionFind { int[] size, parents; this(int n) // make n trees. { size.length = parents.length = n; foreach (i; 0 .. n) makeTree(i); } void makeTree(int x) { parents[x] = x; // the parent of x is x size[x] = 1; } bool isSame(int x, int y) { return findRoot(x) == findRoot(y); } bool unite(int x, int y) { x = findRoot(x); y = findRoot(y); if (x == y) return false; if (size[x] > size[y]) { parents[y] = x; size[x] += size[y]; } else { parents[x] = y; size[y] += size[x]; } return true; } int findRoot(int x) { if (x != parents[x]) parents[x] = findRoot(parents[x]); return parents[x]; } int treeSize(int x) { return size[findRoot(x)]; } } int N, M, T; int[] A, B, C; int[] V; int[][] mat; bool[] ok; int[][] OPT; int first; alias P = Tuple!(int, int); P[] V3; int minimumSteinerTree() { if (T <= 1) return 0; OPT = uninitializedArray!(int[][])(1 << T, N); fill(OPT, 100_000); foreach (p; 0 .. T) foreach (q; 0 .. N) OPT[1 << p][q] = mat[V[p]][q]; foreach (S; 1 .. 1 << T) { if (!(S & (S - 1))) continue; foreach (p; 0 .. N) foreach (E; 0 .. S) if ((E | S) == S) chMin(OPT[S][p], OPT[E][p] + OPT[S - E][p]); foreach (p; 0 .. N) foreach (q; 0 .. N) chMin(OPT[S][p], OPT[S][q] + mat[p][q]); } int ans = 100_000; foreach (S; 0 .. 1 << T) foreach (q; 0 .. N) chMin(ans, OPT[S][q] + OPT[(1 << T) - 1 - S][q]); return ans; } int dodo(long mask, int cur) { auto uf = UnionFind(N); auto que = redBlackTree!P(); int x, y; int cnt = popcnt(mask); int tot = 0, i; foreach (v; V3) { x = v[1] / 64, y = v[1] % 64; if ((mask & (1L << x)) == 0) continue; if ((mask & (1L << y)) == 0) continue; if (!uf.isSame(x, y)) { tot += v[0]; uf.unite(x, y); if (uf.treeSize(first) == cnt) break; } if (tot > cur) return tot; } return tot; } void main() { // 入力 readln.chomp.formattedRead("%d %d %d", N, M, T); mat = uninitializedArray!(int[][])(N, N); fill(mat, 10 ^^ 9); foreach (x; 0 .. N) mat[x][x] = 0; A = new int[](M); B = new int[](M); C = new int[](M); foreach (i; 0 .. M) { readln.chomp.formattedRead("%d %d %d", A[i], B[i], C[i]); --A[i], --B[i]; mat[A[i]][B[i]] = C[i]; mat[B[i]][A[i]] = C[i]; } // ワーシャルフロイド法 foreach (i; 0 .. N) foreach (x; 0 .. N) foreach (y; 0 .. N) chMin(mat[x][y], mat[x][i] + mat[i][y]); foreach (x; 0 .. N) foreach (y; 0 .. N) V3 ~= P(mat[x][y], x * 64 + y); V3.sort; ok = new bool[](N); long mask = 0; foreach (_; 0 .. T) { int x = readln.chomp.to!int - 1; V ~= x; ok[x] = true; mask |= 1L << x; first = x; } // 答えの計算と出力 if (T <= 13) { writeln(minimumSteinerTree()); return; } int[] V2; foreach (i; 0 .. N) if (!ok[i]) V2 ~= i; int mi = 10 ^^ 7; foreach (i; 0 .. 1L << V2.length) { long mask2 = mask; foreach (j; 0 .. V2.length) if (i & (1L << j)) mask2 |= 1L << V2[j]; chMin(mi, dodo(mask2, mi)); } writeln(mi); }