问题 H: 浙外办会展
此题对时间复杂度的要求好高，数组大小n*k(1e7)和时间复杂度n * k * logk(1e7-1e8)有点极限
思路：
题意从k种选s种，问最小代价
1.我们可以开二维数组ans[n][k]，表示每个点i选种类是j的最小代价
2.这个可以bfs，算完之后，只需要sort从小到大，累加求和即可
如果你想到了这里，很遗憾，超时8%
分析，每个点都遍历一下，时间复杂度是n^2 肯定过不了；
考虑优化
我们发现很多点的种类是一样的，相当于多个源点向外扩散，每个点的最小值是距离源点最近的那个点，没错可以利用上次学到的优先队列维护最小值，时间复杂的为n* logn,可以。
一点点细节
int a[N];
int n,m,s,k;
vector<int> g[N];
int ans[N][105];
int vis[N][105];
struct node{
int dis,id,idx;//距离，国家，种类
bool operator < (const node &b)const{
return dis>b.dis;
}
};
priority_queue<node> q;
int bfs(){
while(q.size()){
auto t=q.top();
q.pop();
int dis=t.dis,id=t.id,idx=t.idx;
if(vis[id][idx]) continue;
vis[id][idx]=1;
for(int v:g[id]){
if(ans[id][idx]+1<ans[v][idx]){
ans[v][idx]=ans[id][idx]+1;
q.push({ans[v][idx],v,idx});
}
}
}
}
void bu_f(){
n=read(),m=read(),k=read(),s=read();
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1;i<=m;i++){
int x=read(),y=read();
g[x].push_back(y);
g[y].push_back(x);
}
memset(ans,INF,sizeof ans);
for(int i=1;i<=n;i++){
ans[i][a[i]]=0;//源点为0
q.push({0,i,a[i]});//压入队列
}
bfs();
for(int i=1;i<=n;i++){
sort(ans[i]+1,ans[i]+k+1);//排序
ll sum=0;
for(int j=1;j<=s;j++){
sum+=ans[i][j];//累加求和
}
write(sum);
printf(" ");
}
}