結果

問題 No.114 遠い未来
コンテスト
ユーザー 古寺いろは
提出日時 2015-03-25 10:00:24
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,818 bytes
コンパイル時間 3,038 ms
コンパイル使用メモリ 172,460 KB
実行使用メモリ 5,760 KB
最終ジャッジ日時 2024-06-29 00:47:57
合計ジャッジ時間 33,809 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 22 TLE * 3
権限があれば一括ダウンロードができます

ソースコード

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){
	for (int i = 0; i < N; i++)
	{
		uni[i] = -1;
	}

	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++;
			}
		}
	}
	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;

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


	if (T <= border){
		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