#1194400 (D) No.114 遠い未来

• 問題: No.114 遠い未来
• ユーザー: ゴリポン先生
• 提出日時: 2026-10-23 16:35:07
• 言語: D (dmd 2.113.0)
• 結果: AC
• 実行時間: 363 ms / 5,000 ms
• コード長: 3,719 bytes
• コンパイル時間: 3,360 ms
• コンパイル使用メモリ: 192,592 KB
• 実行使用メモリ: 11,276 KB
• 最終ジャッジ日時: 2026-10-23 16:35:15
• 合計ジャッジ時間: 8,347 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge5_0

ファイルパターン	結果
sample	AC * 3
other	AC * 28

ソースコード

module main;
// claude ai より
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;
}

int N, M, T;
int[] V;          // 終端点
int[] V2;         // 非終端点
int[][] mat;      // 最短距離行列(ワーシャルフロイド後)

// 方式A: Steiner木DP。終端点の1つを根にして残りT-1個で部分集合DPをする。O(3^(T-1) N + 2^(T-1) N^2)
int steinerDP()
{
	int Tm = T - 1;
	int root = V[Tm];
	auto OPT = uninitializedArray!(int[][])(1 << Tm, N);
	fill(OPT, 100_000);

	foreach (p; 0 .. Tm)
		foreach (q; 0 .. N)
			OPT[1 << p][q] = mat[V[p]][q];

	foreach (S; 1 .. 1 << Tm) {
		if (!(S & (S - 1))) continue;
		auto row = OPT[S];
		// Sの最下位ビットを含む側をEとして、(E, S-E) の分割を一度だけ列挙する
		int low = S & -S;
		int rest = S ^ low;
		int sub = rest;
		while (true) {
			sub = (sub - 1) & rest;	// restの真部分集合を降順に列挙(0を含む)
			int E = low | sub;
			auto a = OPT[E];
			auto b = OPT[S ^ E];
			foreach (p; 0 .. N)
				chMin(row[p], a[p] + b[p]);
			if (sub == 0) break;
		}
		// matは最短距離行列(三角不等式が成立)なので1回の緩和で十分
		foreach (p; 0 .. N)
			foreach (q; 0 .. N)
				chMin(row[p], row[q] + mat[p][q]);
	}
	return OPT[(1 << Tm) - 1][root];
}

// 頂点集合vs[0..k)上の最小全域木(Prim法, O(k^2))。totがlimit以上になったら打ち切る
int primMst(ref int[40] vs, int k, int limit)
{
	int[40] rem, d;
	int tot = 0;
	int u = vs[0];
	int m = k - 1;
	auto row = mat[u];
	foreach (j; 0 .. m) {
		rem[j] = vs[j + 1];
		d[j] = row[rem[j]];
	}
	while (m > 0) {
		int bi = 0;
		foreach (j; 1 .. m)
			if (d[j] < d[bi]) bi = j;
		tot += d[bi];
		if (tot >= limit) return tot;
		u = rem[bi];
		--m;
		rem[bi] = rem[m];
		d[bi] = d[m];
		row = mat[u];
		foreach (j; 0 .. m) {
			int w = row[rem[j]];
			if (w < d[j]) d[j] = w;
		}
	}
	return tot;
}

// 方式B: 使う非終端点の部分集合を全列挙して、各集合の最小全域木の最小値を取る。O(2^(N-T) k^2)
int steinerEnum()
{
	int K = cast(int)V2.length;
	int best = int.max;
	int[40] vs;
	foreach (p; 0 .. T)
		vs[p] = V[p];
	foreach (uint i; 0 .. 1u << K) {
		// 最適解で使う非終端点(次数3以上)は高々T-2個
		if (popcnt(i) > T - 2) continue;
		int k = T;
		for (uint b = i; b; b &= b - 1)
			vs[k++] = V2[bsf(b)];
		chMin(best, primMst(vs, k, best));
	}
	return best;
}

bool useEnum()
{
	double costDP = 3.0 ^^ (T - 1) * N / 2 + 2.0 ^^ (T - 1) * N * N;
	double K = N - T;
	double costEnum = 2.0 ^^ K * (T + K / 2) ^^ 2 * 2;	// Primの1手はDPの1手より重いので重み2
	return costEnum < costDP;
}

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;
	foreach (i; 0 .. M) {
		int a, b, c;
		readln.chomp.formattedRead("%d %d %d", a, b, c);
		--a, --b;
		mat[a][b] = c;
		mat[b][a] = c;
	}
	// ワーシャルフロイド法
	foreach (i; 0 .. N)
		foreach (x; 0 .. N)
			foreach (y; 0 .. N)
				chMin(mat[x][y], mat[x][i] + mat[i][y]);
	auto ok = new bool[](N);
	foreach (_; 0 .. T) {
		int x = readln.chomp.to!int - 1;
		V ~= x;
		ok[x] = true;
	}
	foreach (i; 0 .. N)
		if (!ok[i]) V2 ~= i;
	// 答えの計算と出力
	if (T <= 1)
		writeln(0);
	else if (useEnum())
		writeln(steinerEnum());
	else
		writeln(steinerDP());
}