$\large\text{CodeForces1741G-Kirill and Company题解}$

题面传送门（有翻译（由黄巨佬提供））

思路

预处理

因为 $k$ 很小，所以可以先 bfs 预处理出家在 $i(2\le i\le n)$ 的人能捎带上哪些集合的人，在表示集合时用一个 $0$ 到 $2^k-1$ 的整数 $j$ 表示，若 $j$ 在二进质下的从小到大第 $l$ 位是 $1$，那么这个集合就包含第 $l$ 的没车的人。

在 bfs 从 $i$ 转移到 $j$ 时，如果 $i$ 能成为 $1$ 到 $j$ 的最短路上的点，那么家在 $i$ 的人能捎带上的人的集合家在 $j$ 的人也能捎带上，注意集合里还要加上家在 $j$ 点且没车的人。

预处理完后做 dp ：

设 $dp_{i,j}$ 表示前 $i$ 个人是否能捎带上 $j$ 集合里的所有人。
转移（扩散型）：
- 如果第 $i+1$ 个人没车，那么如果 $dp_{i,j}=1$ 则 $dp_{i+1,j}=1$ 否则 $dp_{i+1,j}=0$ 。
- 如果第 $i+1$ 个人有车，那么如果 $dp_{i,j}=1$ 且第 $i+1$ 个人回家的路上能捎带上集合 $l$ 的人，则对于 $j$ 和 $l$ 的并集 $q$，$dp_{i+1,q}=1$。
在表示集合的时候，可以用预处理时的方法，那么 $j$ 和 $l$ 的并集就是 $j|l$。

答案

对于每个 $$ 的

时间复杂度

对于每个测试点

bfs

$O(m\cdot 2^k)$

dp

$O(tot\cdot 2^{2k})$

总

$O(m\cdot 2^k+tot\cdot 2^{2k})$

空间复杂度

$O(n\cdot 2^k+tot\cdot 2^k)$

代码（不建议在做出来之前看）

优美的码风

#include <bits/stdc++.h>

using namespace std;

const int kMaxN=1e4+1,kMaxS=1<<6;

int t,n,m,p[kMaxN],o,h[kMaxN],k,c[kMaxN],dp[kMaxN][kMaxS],ma;
bool a[kMaxN][kMaxS],f[kMaxN];
vector<int>b[kMaxN];
queue<int>q;

void R(int x,int l,int j){
	if(j<=c[x]){
		if(j<c[x]){
			c[x]=j;
			q.push(x);
		}
		for(int i=0;i<(1<<k);i++){
			a[x][(i|p[x])]|=a[l][i];
		}
	}
}

int S(int x){
	int ans=0;
	for(;x;ans++,x-=(x&(-x))){
	}
	return ans;
}

int main() {
	ios::sync_with_stdio(0),cin.tie(0);
	for(cin>>t;t--;){
		cin>>n>>m;
		for(int i=1,u,v;i<=m;i++){
			cin>>u>>v;
			b[u].push_back(v),b[v].push_back(u);
		}
		cin>>o;
		for(int i=1;i<=o;i++){
			cin>>h[i];
		}
		cin>>k;
		fill(p+1,p+n+1,0);
		fill(f+1,f+o+1,0);
		for(int i=1,a;i<=k;i++){
			cin>>a;
			f[a]=1;
			p[h[a]]+=(1<<(i-1));
		}
		fill(a[1],a[n]+kMaxS,0);
		a[1][0]=1;
		fill(c+1,c+n+1,n+1);
		for(R(1,0,0);q.size();q.pop()){
			for(int i:b[q.front()]){
				R(i,q.front(),c[q.front()]+1);
			}
		}
		fill(dp[0],dp[o]+kMaxS,0);
		dp[0][0]=1;
		for(int i=0;i<o;i++){
			for(int j=0;j<(1<<k);j++){
				if(dp[i][j]){
					if(!f[i+1]){
						for(int l=0;l<(1<<k);l++){
							if(a[h[i+1]][l]){
								dp[i+1][j|l]=1;
							}
						}
					}else{
						dp[i+1][j]=1;
					}
				}
			}
		}
		ma=0;
		for(int i=0;i<(1<<k);i++){
			ma=max(ma,S(i)*dp[o][i]);
		}
		cout<<k-ma<<"\n";
		for(int i=1;i<=n;i++){
			b[i].clear();
		}
	}
	return 0;
}