結果
問題 | 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;}}}