結果
問題 | No.2630 Colorful Vertices and Cheapest Paths |
ユーザー |
|
提出日時 | 2024-02-11 12:10:55 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 789 ms / 2,500 ms |
コード長 | 1,236 bytes |
コンパイル時間 | 2,297 ms |
コンパイル使用メモリ | 205,492 KB |
最終ジャッジ日時 | 2025-02-19 05:01:31 |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 |
ソースコード
#include<bits/stdc++.h>using namespace std;using ll=long long;constexpr int MAX_C=10;int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int N,M;cin>>N>>M;vector G(N,vector(0,0));for(int i=0;i<M;i++){int A,B;cin>>A>>B;--A,--B;G[A].push_back(B);G[B].push_back(A);}vector C(N,0);for(int &i:C)cin>>i,--i;vector W(MAX_C,0ll);for(ll &i:W)cin>>i;vector root(1<<MAX_C,vector(N,-1));for(int i=0;i<1<<MAX_C;i++){for(int j=0;j<N;j++){if(root[i][j]!=-1)continue;root[i][j]=j;if(!(i>>C[j]&1))continue;queue<int>bfs;bfs.push(j);while(bfs.size()){int v=bfs.front();bfs.pop();for(int k:G[v]){if((i>>C[k]&1)&&root[i][k]==-1){root[i][k]=j;bfs.push(k);}}}}}vector cost(1<<MAX_C,0ll);for(int i=0;i<1<<MAX_C;i++){for(int j=0;j<MAX_C;j++){if(i>>j&1)cost[i]+=W[j];}}int Q;cin>>Q;while(Q--){int U,V;cin>>U>>V;--U,--V;ll ans=1e12;for(int i=0;i<1<<MAX_C;i++){if(root[i][U]==root[i][V]){ans=min(ans,cost[i]);}}cout<<(ans==1e12?-1ll:ans)<<'\n';}}