結果
問題 | No.2630 Colorful Vertices and Cheapest Paths |
ユーザー |
|
提出日時 | 2024-02-16 23:00:37 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 294 ms / 2,500 ms |
コード長 | 1,396 bytes |
コンパイル時間 | 20,935 ms |
コンパイル使用メモリ | 355,948 KB |
最終ジャッジ日時 | 2025-02-19 14:38:09 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 |
ソースコード
#pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include<bits/stdc++.h> #include<atcoder/all> using namespace std; using namespace atcoder; using ll=long long; void IO(){ ios::sync_with_stdio(false); std::cin.tie(nullptr); } string f(ll n){ string res; while(n){ ll r=n%2; n/=2; res+=r+'0'; } reverse(res.begin(),res.end()); if(res.size()==0){ res+='0'; } return res; } int main(){ IO(); ll n,m; cin>>n>>m; vector<ll> a(m),b(m); for(ll i=0;i<m;i++){ cin>>a[i]>>b[i]; a[i]--; b[i]--; } vector<ll> c(n); for(ll i=0;i<n;i++){ cin>>c[i]; c[i]--; } vector<ll> w(10); for(ll i=0;i<10;i++){ cin>>w[i]; } ll q; cin>>q; vector<ll> u(q),v(q); for(ll i=0;i<q;i++){ cin>>u[i]>>v[i]; u[i]--; v[i]--; } vector<ll> ans(q,1e18); for(ll bit=0;bit<(1<<10);bit++){ ll cost=0; for(ll i=0;i<10;i++){ if(bit&(1<<i)){ cost+=w[i]; } } dsu uf(n); for(ll i=0;i<m;i++){ if((bit&(1<<c[a[i]]))&&(bit&(1<<c[b[i]]))){ if(!uf.same(a[i],b[i])){ uf.merge(a[i],b[i]); } } } for(ll i=0;i<q;i++){ if(uf.same(u[i],v[i])){ ans[i]=min(ans[i],cost); } } } for(ll i=0;i<q;i++){ if(ans[i]==1e18){ cout<<-1<<endl; }else{ cout<<ans[i]<<endl; } } }