結果

問題 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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);
}
0