結果

問題 No.114 遠い未来
ユーザー 古寺いろは古寺いろは
提出日時 2015-03-25 10:04:26
言語 C++11
(gcc 11.4.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,921 bytes
コンパイル時間 1,601 ms
コンパイル使用メモリ 172,148 KB
実行使用メモリ 5,760 KB
最終ジャッジ日時 2024-06-29 00:49:54
合計ジャッジ時間 18,467 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 224 ms
5,248 KB
testcase_01 AC 1,108 ms
5,376 KB
testcase_02 AC 114 ms
5,376 KB
testcase_03 AC 24 ms
5,376 KB
testcase_04 AC 1 ms
5,376 KB
testcase_05 AC 15 ms
5,376 KB
testcase_06 AC 412 ms
5,376 KB
testcase_07 AC 1 ms
5,376 KB
testcase_08 AC 1 ms
5,376 KB
testcase_09 AC 26 ms
5,376 KB
testcase_10 AC 1,409 ms
5,376 KB
testcase_11 TLE -
testcase_12 AC 741 ms
5,376 KB
testcase_13 AC 2,354 ms
5,376 KB
testcase_14 AC 389 ms
5,376 KB
testcase_15 AC 1,264 ms
5,376 KB
testcase_16 AC 201 ms
5,376 KB
testcase_17 AC 183 ms
5,376 KB
testcase_18 AC 1,197 ms
5,376 KB
testcase_19 AC 103 ms
5,376 KB
testcase_20 AC 144 ms
5,376 KB
testcase_21 AC 7 ms
5,376 KB
testcase_22 AC 8 ms
5,376 KB
testcase_23 AC 2 ms
5,376 KB
testcase_24 AC 3 ms
5,376 KB
testcase_25 AC 2 ms
5,376 KB
testcase_26 AC 2 ms
5,376 KB
testcase_27 AC 1 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"
using namespace std;

#define border 14

int dist[36][36];
int need[36];
int check[36];
int ans;

int uni[36];

int getuni(int a){
	if (uni[a] < 0) return a;
	else return uni[a] = getuni(uni[a]);
}

int connect(int a, int b){
	a = getuni(a);
	b = getuni(b);
	if (a == b) return 0;
	if (uni[a] > uni[b]) swap(a, b);
	uni[a] += uni[b];
	uni[b] = a;
	return 1;
}


vector<tuple<int, int, int>> v;

int spanningTree(int N){
	int needcount = 0;
	for (int i = 0; i < N; i++)
	{
		uni[i] = -1;
		if (check[i]) needcount++;
	}

	int cost = 0;
	int count = 0;
	for (auto now : v){
		if (check[get<1>(now)] && check[get<2>(now)])
		{
			if (connect(get<1>(now), get<2>(now))){
				cost += get<0>(now);
				count++;
			}
		}
	}
	if (needcount != count + 1) cost = 999999;
	ans = min(ans, cost);
	return cost;
}

int OPT[(1 << border)][35];

int minimum_steiner_tree(const vector<int>& T, int N) {
	int n = N;
	int numT = T.size();
	if (numT <= 1) return 0;

	for (int S = 0; S < (1 << numT); ++S)
	for (int x = 0; x < n; ++x)
		OPT[S][x] = 999999;

	for (int p = 0; p < numT; ++p) // trivial case
	for (int q = 0; q < n; ++q)
		OPT[1 << p][q] = dist[T[p]][q];

	for (int S = 1; S < (1 << numT); ++S) { // DP step
		if (!(S & (S - 1))) continue;
		for (int p = 0; p < n; ++p)
		for (int E = 0; E < S; ++E)
		if ((E | S) == S)
			OPT[S][p] = min(OPT[S][p], OPT[E][p] + OPT[S - E][p]);
		for (int p = 0; p < n; ++p)
		for (int q = 0; q < n; ++q)
			OPT[S][p] = min(OPT[S][p], OPT[S][q] + dist[p][q]);
	}
	int ans2 = 999999;
	for (int S = 0; S < (1 << numT); ++S)
	for (int q = 0; q < n; ++q)
		ans2 = min(ans2, OPT[S][q] + OPT[((1 << numT) - 1) - S][q]);

	ans = ans2;
	return ans;
}



int main() {
	int N, M, T;
	cin >> N >> M >> T;
	int MAX = 999999;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			dist[i][j] = MAX;
		}
		dist[i][i] = 0;
	}

	for (int i = 0; i < M; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		a--; b--;
		dist[a][b] = c;
		dist[b][a] = c;
	}

	


	vector<int> T2;
	for (int i = 0; i < T; i++)
	{
		int temp;
		cin >> temp;
		temp--;
		T2.push_back(temp);
		need[temp] = 1;
		check[temp] = 1;
	}

	ans = 999999;



	if (T <= border){
		for (int k = 0; k < N; k++)
		{
			for (int i = 0; i < N; i++)
			{
				for (int j = 0; j < N; j++)
				{
					dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
				}
			}
		}
		ans = minimum_steiner_tree(T2, N);
	}
	else{
		vector<int> nokori;
		for (int i = 0; i < N; i++)
		{
			if (!need[i]) nokori.push_back(i);
		}


		for (int i = 0; i < N; i++)
		{
			for (int j = i + 1; j < N; j++)
			{
				if (dist[i][j] > 100) continue;
				v.push_back(make_tuple(dist[i][j], i, j));
			}
		}
		sort(v.begin(), v.end());

		for (int i = 0; i < (1 << nokori.size()); i++)
		{
			for (int j = 0; j < nokori.size(); j++)
			{
				check[nokori[j]] = (i >> j) % 2;
			}
			int temp = spanningTree(N);
		}

	}
	cout << ans << endl;
}
0