結果
問題 | No.2630 Colorful Vertices and Cheapest Paths |
ユーザー |
|
提出日時 | 2024-02-16 21:34:28 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 394 ms / 2,500 ms |
コード長 | 1,834 bytes |
コンパイル時間 | 1,568 ms |
コンパイル使用メモリ | 169,360 KB |
実行使用メモリ | 83,856 KB |
最終ジャッジ日時 | 2024-09-28 19:48:58 |
合計ジャッジ時間 | 7,835 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 |
ソースコード
/*Things to notice:1. do not calculate useless values2. do not use similar namesThings to check:1. submit the correct file2. time (it is log^2 or log)3. memory4. prove your naive thoughts5. long long6. corner case like n=0,1,inf or n=m7. check if there is a mistake in the ds or other tools you use8. fileio in some oi-contest9. module on time10. the number of a same divisor in a math problem11. multi-information and queries for dp and ds problems*/#include<bits/stdc++.h>using namespace std;#define int long long#define fi first#define se second#define pii pair<long long,long long>#define mp make_pair#define pb push_backconst int mod=998244353;const int inf=0x3f3f3f3f;const int INF=1e18;struct DSU{int fa[10005];void init(){for(int i=1;i<=10000;i++) fa[i]=i;}int find(int x){if(fa[x]==x) return x;return fa[x]=find(fa[x]);}void merge(int x,int y){int xx=find(x),yy=find(y);if(xx!=yy) fa[xx]=yy;}}dsu[1<<10];int n,m;int U[10005],V[10005];int col[10005],sum[1<<10];int W[10];void solve(){cin>>n>>m;for(int i=1;i<=m;i++) cin>>U[i]>>V[i];for(int i=1;i<=n;i++) cin>>col[i],col[i]--;for(int i=0;i<10;i++) cin>>W[i];for(int mask=0;mask<(1<<10);mask++){for(int j=0;j<10;j++) if(mask&(1<<j)) sum[mask]+=W[j];dsu[mask].init();for(int i=1;i<=m;i++){int u=U[i],v=V[i];if((mask&(1<<col[u]))&&(mask&(1<<col[v]))) dsu[mask].merge(u,v);}}int Q;cin>>Q;while(Q--){int u,v;cin>>u>>v;int ans=INF;for(int mask=0;mask<(1<<10);mask++) if((mask&(1<<col[u]))&&(mask&(1<<col[v]))){if(dsu[mask].find(u)==dsu[mask].find(v)) ans=min(ans,sum[mask]);}if(ans==INF) ans=-1;cout<<ans<<"\n";}}signed main(){ios::sync_with_stdio(0);cin.tie(0);int _=1;// cin>>_;while(_--) solve();return 0;}