結果
問題 | No.114 遠い未来 |
ユーザー |
![]() |
提出日時 | 2021-10-26 21:16:16 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3,707 ms / 5,000 ms |
コード長 | 1,779 bytes |
コンパイル時間 | 4,434 ms |
コンパイル使用メモリ | 265,336 KB |
最終ジャッジ日時 | 2025-01-25 07:23:08 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 25 |
ソースコード
#include <stdio.h> #include <bits/stdc++.h> #include <atcoder/all> using namespace atcoder; using namespace std; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf 1000000000 int main(){ int N,M,T; cin>>N>>M>>T; vector dis(N,vector<int>(N,Inf)); rep(i,M){ int a,b,c; cin>>a>>b>>c; a--;b--; dis[a][b] = c; dis[b][a] = c; } rep(i,N)dis[i][i] = 0; rep(i,N){ rep(j,N){ rep(k,N){ dis[j][k] = min(dis[j][k], dis[j][i]+dis[i][k]); } } } vector<int> v(T); rep(i,T){ cin>>v[i]; v[i]--; } sort(v.begin(),v.end()); vector<int> cov; rep(i,N){ if(!binary_search(v.begin(),v.end(),i))cov.push_back(i); } int ans = Inf; if(T<=15){ vector dp(N,vector<int>(1<<T,Inf)); rep(i,N){ dp[i][0] = 0; rep(j,T){ dp[i][1<<j] = dis[i][v[j]]; } } rep(i,1<<T){ if(__builtin_popcount(i)<=1)continue; for(int S = i&(i-1);S!=0;S = (S-1)&i){ rep(j,N){ dp[j][i] = min(dp[j][i],dp[j][S] + dp[j][S^i]); } } rep(j,N){ rep(k,N){ dp[j][i] = min(dp[j][i],dp[k][i] + dis[k][j]); } } } rep(i,N)ans = min(ans,dp[i].back()); } else{ vector<pair<int,pair<int,int>>> E; rep(j,N){ for(int k=j+1;k<N;k++){ E.emplace_back(dis[j][k],make_pair(j,k)); } } sort(E.begin(),E.end()); vector<bool> f(N,false); rep(i,v.size())f[v[i]] = true; rep(i,1<<cov.size()){ rep(j,cov.size()){ if((i>>j)&1)f[cov[j]] = true; } dsu D(N); int temp = 0; rep(j,E.size()){ int x = E[j].second.first,y = E[j].second.second; if(f[x]&&f[y]){ if(!D.same(x,y)){ D.merge(x,y); temp += E[j].first; } } } ans = min(ans,temp); rep(j,cov.size()){ if((i>>j)&1)f[cov[j]] = false; } } } cout<<ans<<endl; return 0; }