【题意】：

有些公司将在Byteland举办公平的会议。Byteland的n个城镇，m条两镇之间的双向道路。当然，你可以使用道路从任一个城镇到达任何城镇。有k种商品产自Byteland，并且每个城镇只生产一种类型。为了举办公平，你必须至少带来s种不同种类的商品。【It costs d(u,v) coins to bring goods from town u to town v where d(u,v)d (u , v ) is the length of the shortest path from u to v .】  它花费货物从市区u到市区v的硬币成本为d（u，v），其中d（u，v）是从u到v的最短路的长度。 【Length of a path is the number of roads in this path.】   路径的长度是此路径中的道路数量。主办单位将承担所有差旅费用，但他们可以选择城镇提货。现在他们想要计算在n个城镇举办公平的最低费用。输入 城镇数量n，道路数量m，不同类型商品的数量k，持有公平所需的不同类型商品的数量s。其中ai 是第i个城镇生产的商品类型。确保1和k之间的所有整数在整数ai中至少出现一次。通过这条路相连的城镇。保证每两个城镇之间不超过一条公路。保证您可以通过道路从任何城镇到任何其他城镇。打印n个数，其中第i个数是您需要花费在旅行费用上的最小数量的硬币用空格分隔数字。

【分析】：我们要另辟蹊径，从k种不同类型的商品为起点进行BFS，然后求k个点到不同城镇的最短路径，为什么呢？因为k最多100种，如果从城镇为起点BFS，那么1e5的决策次数是会T的。

【代码】：

#include 
    
     #include
     
      #include
      
       #include
       
        using namespace std;#define N 100010#define M 2005const int  INF =  0x3f3f3f3f;#define rep(i,a,b) for(int i=(a); i<(b); i++)#define ll long longint n,m,k,s,u,v;int a[N];vector
        
          G[N];int d[N];int dis[105][N];//dist[i]是源到i的目前最短路长度void bfs(int st){    queue
         
           q; for(int i=1;i<=n;i++) { if(a[i]==st) //起点等于某一类(枚举k个商品) { dis[st][i]=0; q.push(i); //记录下标 } } while( !q.empty() ) { //每次迭代，取出队头的点u，依次枚举从u出发的边 int u=q.front();q.pop(); for(int i=0; i
          
            dis[st][u] + 1) { dis[st][v] = dis[st][u] + 1;//没判队列里是否已经有v,可能会慢一些 q.push(v); //此时由于st到v的最短距离变小了，有可能v可以改进其它的点，所以若v不在队列中，就将它放入队尾 } //这样一直迭代下去直到队列变空，也就是S到所有节点的最短距离都确定下来，结束算法 } }}int main(){ memset(dis,120,sizeof(dis)); scanf("%d%d%d%d",&n,&m,&k,&s); for(int i=1;i<=n;i++) { cin>>a[i]; } for(int i=1;i<=m;i++) { cin>>u>>v; G[u].push_back(v); G[v].push_back(u); } for(int i=1; i<=k; i++) bfs(i);//从k个不同类型点枚举,保存dis最短路径 for(int i=1; i<=n; i++) { for(int j=1; j<=k; j++) d[j]=dis[j][i]; sort(d+1,d+k+1); long long ans=0; for(int j=1; j<=s; j++) ans+=d[j]; cout << ans << ' '; } cout<