結果

問題 No.114 遠い未来
コンテスト
ユーザー Ysmr_Ry
提出日時 2014-12-29 19:49:17
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 1,323 ms / 5,000 ms
コード長 2,524 bytes
コンパイル時間 709 ms
コンパイル使用メモリ 53,236 KB
実行使用メモリ 9,292 KB
最終ジャッジ日時 2024-06-13 01:05:50
合計ジャッジ時間 9,251 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:68:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   68 |         scanf( "%d%d%d", &N, &M, &T );
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
main.cpp:75:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   75 |                 scanf( "%d%d%d", &a, &b, &c );
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
main.cpp:83:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   83 |                 scanf( "%d", &v );
      |                 ~~~~~^~~~~~~~~~~~

ソースコード

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