MC0487宝玉的考验
码蹄杯前的最后一题，可能也是算法竞赛生涯最后一篇博客了
题意：
#include<bits/stdc++.h> #define int long long #define fi first #define se second #define endl '\n' using namespace std; typedef pair<int,int> pii; const int N=1e6+10; const int mod=998244353; vector<int>pm; int judge[N],nm[N],inv[N]; int Log2[N]; int kmi(int a,int b){ int res=1; while(b){ if(b&1) res=res*a%mod; a=a*a%mod; b>>=1; } return res; } void init(){ nm[0]=inv[0]=1; for(int i=1;i<=1e6;i++){ nm[i]=nm[i-1]*i%mod; inv[i]=kmi(nm[i],mod-2); } } void euler(int n){ judge[1]=1; for(int i=2;i<=n;i++){ if(!judge[i]){ pm.push_back(i); } for(int j=0;pm[j]*i<=n;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 dis>b.dis; } }; void solve(){ int n,m,k,t;cin>>n>>m>>k>>t; vector<vector<pii> >g(n+10); for(int i=1;i<=m;i++){ int u,v,w;cin>>u>>v>>w; g[u].push_back({v,w}),g[v].push_back({u,w}); } vector<int>id(n+10); for(int i=1;i<=k;i++){ int u;cin>>u; id[u]=i; } vector<int>pre(n+10); for(int i=1;i<=t;i++){ int x,y;cin>>x>>y; int kt=id[x]; pre[y]|=(1<<(kt-1)); } priority_queue<nod>q; int k1=id[1],st1=0; if(k1) st1=(1<<(k1-1)); q.push({0,st1,1}); vector<vector<int> >dis(n+10,vector<int>((1<<k),1e18)); dis[1][st1]=0; vector<vector<int> >vis(n+10,vector<int>(1<<k)); 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 st=0; if(id[v]) st=pre[v]; bool ok=1; for(int bit=0;bit<k;bit++){ if((st>>bit)&1){ if(((stu>>bit)&1)==0) ok=0; } } if(!ok) continue; int nowk=0; if(id[v]) nowk=(1<<(id[v]-1)); int nxst=(stu|nowk); if(vis[v][nxst]) continue; if(dis[v][nxst]>d+w){ dis[v][nxst]=d+w; q.push({dis[v][nxst],nxst,v}); } } } int ans=1e18; for(int msk=0;msk<(1<<(k));msk++){ ans=min(ans,dis[n][msk]); } if(ans>1e17){ cout<<"impossible"; } else cout<<ans; cout<<endl; } signed main(){ ios::sync_with_stdio(0);cin.tie(0); // for(int i=2;i<=1e6;i++){ // Log2[i]=Log2[i/2]+1; // } int T=1;cin>>T; while(T--) solve(); return 0; }