結果
問題 |
No.1690 Power Grid
|
ユーザー |
![]() |
提出日時 | 2021-10-02 10:18:33 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 179 ms / 3,000 ms |
コード長 | 1,954 bytes |
コンパイル時間 | 3,859 ms |
コンパイル使用メモリ | 237,864 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-20 03:59:53 |
合計ジャッジ時間 | 6,595 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 25 |
ソースコード
#include <bits/stdc++.h> using namespace std; #include <atcoder/all> using namespace atcoder; using ll=long long; using Graph=vector<vector<int>>; #define MAX 20005 //#define MOD 1000000007 #define MOD 998244353 //#define INF 1000000000 #define INF 1000000000000000000 class UnionFind{ int n; vector<int> parent; public: UnionFind(int n_):n(n_){ parent.resize(n); iota(parent.begin(),parent.end(),0); } int find(int x){ int y=parent[x]; if(y!=parent[y]){ y=find(y); } return parent[x]=y; } void unite(int a,int b){ int x=find(a); int y=find(b); if(x!=y){ parent[x]=y; } } bool same(int a,int b){ int x=find(a); int y=find(b); return x==y; } }; int main(){ int N,M,K; cin>>N>>M>>K; vector<ll> A(N); for(int i=0;i<N;i++){ cin>>A[i]; } vector<vector<ll>> dist(N,vector<ll>(N,INF)); for(int i=0;i<M;i++){ int x,y; ll z; cin>>x>>y>>z; x--;y--; dist[x][y]=z; dist[y][x]=z; } 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]); } } } ll ans=INF; for(int bit=0;bit<(1<<N);bit++){ vector<int> index; for(int i=0;i<N;i++){ if(((bit>>i)&1)==1){ index.push_back(i); } } if(index.size()!=K){ continue; } priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq; for(int i=0;i<K;i++){ for(int j=i+1;j<K;j++){ int u=index[i]; int v=index[j]; pq.push(make_pair(dist[u][v],i*K+j)); } } UnionFind tree(K); ll sub=0; while(!pq.empty()){ int i=pq.top().second/K; int j=pq.top().second%K; if(!tree.same(i,j)){ sub+=pq.top().first; tree.unite(i,j); } pq.pop(); } for(int i=0;i<K;i++){ sub+=A[index[i]]; } ans=min<ll>(ans,sub); } cout<<ans<<'\n'; }