結果

問題 No.114 遠い未来
ユーザー Ysmr_RyYsmr_Ry
提出日時 2014-12-29 19:49:17
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 1,917 ms / 5,000 ms
コード長 2,524 bytes
コンパイル時間 588 ms
コンパイル使用メモリ 56,620 KB
実行使用メモリ 9,156 KB
最終ジャッジ日時 2023-09-03 20:15:58
合計ジャッジ時間 11,373 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 29 ms
4,376 KB
testcase_01 AC 1,238 ms
9,148 KB
testcase_02 AC 183 ms
4,380 KB
testcase_03 AC 37 ms
4,380 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 5 ms
4,380 KB
testcase_06 AC 540 ms
4,376 KB
testcase_07 AC 2 ms
4,376 KB
testcase_08 AC 2 ms
4,376 KB
testcase_09 AC 7 ms
4,376 KB
testcase_10 AC 134 ms
4,376 KB
testcase_11 AC 401 ms
7,120 KB
testcase_12 AC 1,241 ms
9,156 KB
testcase_13 AC 1,243 ms
9,136 KB
testcase_14 AC 495 ms
4,376 KB
testcase_15 AC 1,917 ms
4,380 KB
testcase_16 AC 246 ms
4,376 KB
testcase_17 AC 299 ms
4,376 KB
testcase_18 AC 1,184 ms
4,376 KB
testcase_19 AC 128 ms
4,376 KB
testcase_20 AC 140 ms
4,376 KB
testcase_21 AC 9 ms
4,380 KB
testcase_22 AC 12 ms
4,380 KB
testcase_23 AC 2 ms
4,376 KB
testcase_24 AC 3 ms
4,376 KB
testcase_25 AC 2 ms
4,376 KB
testcase_26 AC 1 ms
4,376 KB
testcase_27 AC 2 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<cstdio>
#include<algorithm>
#include<numeric>
#include<vector>
#define repi(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,a) repi(i,0,a)
#define all(a) (a).begin(), (a).end()

typedef long long ll;

const int MAX_N = 35, INF = 1<<28;

int N, M, T;
int d[MAX_N][MAX_N], opt[1<<16][MAX_N];
std::vector<int> ts;
ll Tvs;

struct UnionFind
{
	std::vector<int> par, rank;

	UnionFind( std::size_t sz )
	:	par(sz), rank(sz)
	{ std::iota( all(par), 0 ); }

	int find( int x )
	{ return x==par[x] ? x : par[x]=find(par[x]); }

	void unite( int x, int y )
	{
		x = find(x); y = find( y );
		if( x == y )
			return;

		if( rank[x] < rank[y] )
			par[x] = y;
		else
		{
			par[y] = x;

			if( rank[x] == rank[y] )
				++rank[x];
		}

		return;
	}

	bool same( int x, int y )
	{ return find(x) == find(y); }
};

struct edge
{
	int from, to, cost;

	edge( int from, int to, int cost )
	:	from(from), to(to), cost(cost)
	{}

	bool operator< ( const edge &e ) const
	{ return cost < e.cost; }
};

std::vector<edge> es;

int main()
{
	scanf( "%d%d%d", &N, &M, &T );
	
	rep( i, N ) rep( j, N )
		d[i][j] = i==j?0:INF;
	rep( i, M )
	{
		int a, b, c;
		scanf( "%d%d%d", &a, &b, &c );
		--a; --b;
		d[a][b] = d[b][a] = c;
		es.push_back( edge( a, b, c ) );
	}
	rep( i, T )
	{
		int v;
		scanf( "%d", &v );
		ts.push_back(--v);
		Tvs |= 1ll<<v;
	}
	
	Tvs ^= (1ll<<N)-1;

	int ans = INF;
		
	if( T <= 15 )
	{
		if( T <= 1 )
			ans = 0;
		else
		{
			rep( k, N ) rep( i, N ) rep( j, N )
				d[i][j] = std::min( d[i][j], d[i][k]+d[k][j] );

			rep( S, 1<<T ) rep( i, N )
				opt[S][i] = INF;
			rep( p, T ) rep( q, N )
				opt[1<<p][q] = d[ts[p]][q];

			repi( S, 1, 1<<T )
			{
				if( !(S & S-1) )
					continue;

				rep( p, N ) for( int E = S & S-1; E; E = (E-1)&S )
					opt[S][p] = std::min( opt[S][p], opt[E][p]+opt[S-E][p] );
				rep( p, N ) rep( q, N )
					opt[S][p] = std::min( opt[S][p], opt[S][q]+d[p][q] );
			}

			rep( S, 1<<T ) rep( q, N )
				ans = std::min( ans, opt[S][q]+opt[((1<<T)-1)-S][q] );
		}
	}
	else
	{
		std::sort( all(es) );

		for( ll S = Tvs; S >= 0; --S )
		{
			S &= Tvs;

			UnionFind uf(N);
			int cost = 0;

			rep( i, es.size() )
			{
				const edge &e = es[i];

				if( S>>e.from&1 || S>>e.to&1 )
					continue;

				if( !uf.same( e.from, e.to ) )
				{
					cost += e.cost;
					uf.unite( e.from, e.to );
				}
			}

			bool fl = true;
			rep( i, T ) if( !uf.same( ts[0], ts[i] ) )
			{ fl = false; break; }

			if( fl )
				ans = std::min( ans, cost );
		}
	}

	printf( "%d\n", ans );

	return 0;
}
0