CodeForces 986A Fair

题目大意

题目链接 每个城市都可以生产一种物品，要选择一个城市举办party，要求举办party的城市至少有s 种不同的商品，因此需要从其他城市将商品运送到举办party的城市。 问若每个城市举办party运送的距离是多少？

题解

bfs+思维 枚举每种商品，求出每个城市获取到每种商品的最短距离，对于每个城市而言，将每种商品按照获取所需最短距离从小到大排序，前s个距离之和即为此城市的最小花费（无需知道取的哪几种商品） ————————————— 看懂代码后再看下面： 本质上，我们每次都是将生产某一种商品的城市全部入队，更新其他城市获取到其所生产的商品的最短距离。因此每一次“将生产某一种商品的城市全部入队”进行bfs都是在对每座城市获取到此类商品的最短距离进行更新。

代码

#include
using namespace std;
const int N = 1e5+10;

int dis[N][105], kind[N], vis[N];
int idx, e[Nm>>k>>s;
	for(int i = 1;i >kind[i];
	while(m--) cin>>a>>b, add(a, b), add(b, a);
	
	queue q;
	
	for(int i = 1;i