結果

問題 No.114 遠い未来
ユーザー pessimist
提出日時 2025-06-25 16:03:01
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 646 ms / 5,000 ms
コード長 2,318 bytes
コンパイル時間 2,628 ms
コンパイル使用メモリ 211,760 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-06-25 16:03:10
合計ジャッジ時間 7,493 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define FOR_(n) for (ll _ = 0; (_) < (ll)(n); ++(_))
#define FOR(i, n) for (ll i = 0; (i) < (ll)(n); ++(i))
#define all(x) x.begin(), x.end()
#define len(x) ll(x.size())
#define eb emplace_back
template <class T, class S> inline bool chmax(T &a, const S &b) { return (a < b ? a = b, 1 : 0); }
template <class T, class S> inline bool chmin(T &a, const S &b) { return (a > b ? a = b, 1 : 0); }

const int INF=1e7;
int n,m,t;
int w[36][36];
vector<tuple<int, int, int>> edge;
vector<int> imp;
int dp[1<<14][36];
void steiner_tree(){
	FOR(k,n) FOR(i,n) FOR(j,n) chmin(w[i][j],w[i][k]+w[k][j]);
	FOR(i,1<<14) FOR(j,36) dp[i][j]=INF; 
	FOR(i,len(imp)) FOR(j,n){
		dp[1<<i][j]=w[imp[i]][j];
	}

	FOR(mask, 1<<t){
		if(__builtin_popcount(mask)<2) continue;
		for(int sub=mask;sub;sub=(sub-1)&mask){
			FOR(y,n) chmin(dp[mask][y],dp[sub][y]+dp[mask^sub][y]);
		}
		FOR(j,n) FOR(k,n) chmin(dp[mask][j],dp[mask][k]+w[j][k]);
	}
	int ans=INF;
	FOR(x,n) chmin(ans,dp[(1<<t)-1][x]);
	cout<<ans<<endl;
}

struct uf{
	int par[36];
	void init(){ FOR(i, 36) par[i] = i; }
	int find(int x){ if(x == par[x]) return x; else return par[x] = find(par[x]); }
	void unite(int x, int y){
		x = find(x); y = find(y); if(x == y) return;
		par[x] = y;
	}
	bool same(int x, int y){ return find(x) == find(y); }
}uf;

void solve_MST(){
	sort(all(edge));
	vector<int> ump;
	bool ex[36]{};
	FOR(i,len(imp)) ex[imp[i]]=1;
	FOR(i,n) if(!ex[i]) ump.eb(i);

	const int sz=len(ump);
	int ans=INF;
	FOR(mask,1<<sz){
		const int N=t+__builtin_popcount(mask);
		int cnt=0, use=0;
		bool eex[36]{};
		FOR(i,sz) if(mask>>i&1) eex[ump[i]]=1;
		uf.init();
		FOR(i,len(edge)){
			auto [wt,a,b]=edge[i];
			if(!ex[a] && !eex[a]) continue;
			if(!ex[b] && !eex[b]) continue;
			if(uf.same(a,b)) continue;
			uf.unite(a,b);
			cnt++;
			use+=wt;
			if(ans<=use) break;
		}
		if(cnt==N-1) chmin(ans,use);
	}
	cout<<ans<<endl;
}

void solve(){
	cin>>n>>m>>t;
	FOR(i,36) FOR(j,36) if(i!=j) w[i][j]=INF;
	FOR(_,m){
		int a,b,c;cin>>a>>b>>c;
		--a,--b;
		edge.emplace_back(c,a,b);
		w[a][b]=w[b][a]=c;
	}
	imp.resize(t);
	for(auto&i:imp) cin>>i,--i;
	if(t<=14) steiner_tree();
	else solve_MST();
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t=1; //cin>>t;
    for(;t--;) solve();
}
0