MC0487宝玉的考验

码蹄杯前的最后一题可能也是算法竞赛生涯最后一篇博客了题意#includebits/stdc.h #define int long long #define fi first #define se second #define endl \n using namespace std; typedef pairint,int pii; const int N1e610; const int mod998244353; vectorintpm; int judge[N],nm[N],inv[N]; int Log2[N]; int kmi(int a,int b){ int res1; while(b){ if(b1) resres*a%mod; aa*a%mod; b1; } return res; } void init(){ nm[0]inv[0]1; for(int i1;i1e6;i){ nm[i]nm[i-1]*i%mod; inv[i]kmi(nm[i],mod-2); } } void euler(int n){ judge[1]1; for(int i2;in;i){ if(!judge[i]){ pm.push_back(i); } for(int j0;pm[j]*in;j){ judge[pm[j]*i]1; if(i%pm[j]0) break; } } } int C(int a,int b){ return nm[a]*inv[a-b]%mod*inv[b]%mod; } struct nod{ int dis,st,u; bool operator(const nod b)const{ return disb.dis; } }; void solve(){ int n,m,k,t;cinnmkt; vectorvectorpii g(n10); for(int i1;im;i){ int u,v,w;cinuvw; g[u].push_back({v,w}),g[v].push_back({u,w}); } vectorintid(n10); for(int i1;ik;i){ int u;cinu; id[u]i; } vectorintpre(n10); for(int i1;it;i){ int x,y;cinxy; int ktid[x]; pre[y]|(1(kt-1)); } priority_queuenodq; int k1id[1],st10; if(k1) st1(1(k1-1)); q.push({0,st1,1}); vectorvectorint dis(n10,vectorint((1k),1e18)); dis[1][st1]0; vectorvectorint vis(n10,vectorint(1k)); while(q.size()){ auto [d,stu,u]q.top(); q.pop(); if(vis[u][stu]) continue; vis[u][stu]1; for(auto [v,w]:g[u]){ int st0; if(id[v]) stpre[v]; bool ok1; for(int bit0;bitk;bit){ if((stbit)1){ if(((stubit)1)0) ok0; } } if(!ok) continue; int nowk0; if(id[v]) nowk(1(id[v]-1)); int nxst(stu|nowk); if(vis[v][nxst]) continue; if(dis[v][nxst]dw){ dis[v][nxst]dw; q.push({dis[v][nxst],nxst,v}); } } } int ans1e18; for(int msk0;msk(1(k));msk){ ansmin(ans,dis[n][msk]); } if(ans1e17){ coutimpossible; } else coutans; coutendl; } signed main(){ ios::sync_with_stdio(0);cin.tie(0); // for(int i2;i1e6;i){ // Log2[i]Log2[i/2]1; // } int T1;cinT; while(T--) solve(); return 0; }