CF 986A Fair（多源BFS）

题目描述

一些公司将在Byteland举办商品交易会（or博览会？）。在Byteland有 nnn 个城市，城市间有 mmm 条双向道路。当然，城镇之间两两连通。 Byteland生产的货物有 kkk 种类型，每个城镇只生产一种。为了举办商品交易会，你必须至少带来 sss 种不同类型的商品。将货物从 uuu 镇带到城镇 vvv 将花费 d(u,v)d(u,v)d(u,v) 的费用，其中 d(u,v)d(u,v)d(u,v) 是从 uuu 到 vvv 的最短路径的长度。路径的长度是这个路径中的道路的数量。组织者将支付所有的运输费用，但他们可以选择从哪些城镇带来货物。现在他们想计算每个城镇举办商品交易会的最小费用。

题解

我们考虑每种货物分开做。把生产同一种货物的城市扔到队列里跑BFS，得到每一种货物到每个点的最短距离。

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #include<algorithm>

 #include<queue>

 using namespace std;

 const int N=;

 const int K=;

 int n,m,k,s,c[N],vis[N][K],head[N],cnt,ans;

 queue<int> q;

 struct edge{

     int to,nxt;

 }e[N*];

 void add(int u,int v){

     cnt++;

     e[cnt].nxt=head[u];

     e[cnt].to=v;

     head[u]=cnt;

 }

 int main(){

     scanf("%d%d%d%d",&n,&m,&k,&s);

     for(int i=;i<=n;i++){

         scanf("%d",&c[i]);

     }

     for(int i=,u,v;i<=m;i++){

         scanf("%d%d",&u,&v);

         add(u,v);

         add(v,u);

     }

     memset(vis,-,sizeof(vis));

     for(int i=;i<=k;i++){

         for(int j=;j<=n;j++){

             if(c[j]==i)q.push(j),vis[j][i]=;

         }

         while(!q.empty()){

             int u=q.front();

             q.pop();

             for(int x=head[u];x;x=e[x].nxt){

                 int v=e[x].to;

                 if(vis[v][i]>-)continue;

                 vis[v][i]=vis[u][i]+;

                 q.push(v);

             }

         }

     }

     for(int i=;i<=n;i++){

         ans=;

         sort(vis[i]+,vis[i]++k);

         for(int j=;j<=s;j++){

             ans+=vis[i][j];

         }

         printf("%d ",ans);

     }

     return ;

 }

巴特西

CF 986A Fair（多源BFS）

题目描述

题解

最新文章

热门文章