CF986A Fair【图论/BFS】

【题意】：

有些公司将在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 <iostream>

#include<queue>

#include<string.h>

#include<bits/stdc++.h>

using namespace std;

#define N 100010

#define M 2005

const int  INF =  0x3f3f3f3f;

#define rep(i,a,b) for(int i=(a); i<(b); i++)

#define ll long long

int n,m,k,s,u,v;

int a[N];

vector<int> G[N];

int d[N];

int dis[105][N];//dist[i]是源到i的目前最短路长度

void bfs(int st)

{

    queue<int> 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<G[u].size(); i++)

        {

            int v=G[u][i];

            //若dis[v]+1 < dis[v]，则改进dis[v]

            if(dis[st][v] > 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<<endl;

}

巴特西

CF986A Fair【图论/BFS】

最新文章

热门文章