結果

問題 No.114 遠い未来
コンテスト
ユーザー ゴリポン先生
提出日時 2026-10-23 16:15:15
言語 D
(dmd 2.113.0)
コンパイル:
dmd -fPIE -m64 -w -wi -O -release -inline -I/opt/dmd/src/druntime/import/ -I/opt/dmd/src/phobos -L-L/opt/dmd/linux/lib64/ -fPIC _filename_
実行:
./Main
結果
TLE  
実行時間 -
コード長 3,215 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,396 ms
コンパイル使用メモリ 192,304 KB
実行使用メモリ 55,188 KB
最終ジャッジ日時 2026-10-23 16:15:56
合計ジャッジ時間 35,138 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 19 TLE * 1 -- * 8
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

module main;
// https://kmjp.hatenablog.jp/entry/2014/12/29/0900 より
// 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;
}

/* 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;

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;
		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 << T) - 1].reduce!min;
}
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]);
	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;
	}
	// 答えの計算と出力
	writeln(minimumSteinerTree());
}
0