HLJOJ1015(多源最短路径失真)

意甲冠军：n,m,k，有着n村。有着k路，每个村都有一个电话亭，现在，我们要建立在村中心展台，快递每一个需要同村的中心村，然后返回报告（有向图），有着m电话，假设村配置的手机，那么你并不需要报告。最低要求快递走的道路的总数

思考：floyd预处理下，然后求到每一个村庄的最短路总和，比較最小的。这个就是中心电话亭。然后将这些和由大到小排序。减去前m大的

#include <stdio.h>

#include <string.h>

#include <algorithm>

#include <iostream>

#include <math.h>

#include <queue>

using namespace std;

const double eps = 1e-6;

const int maxn = 200;

const int INF = 10000000;

int dis[maxn][maxn];

int n, m , k;

void floyd()

{

    for(int k = 0; k < n; k++)

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

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

                dis[i][j] = min(dis[i][j],dis[i][k]+ dis[k][j]);

}

int main()

{

#ifdef xxz

    freopen("in.txt","r",stdin);

#endif // xxz

    int Case = 1;

    while(~scanf("%d%d%d",&n,&m,&k))

    {

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

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

                i == j ? dis[i][j] = 0 : dis[i][j] = INF;

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

        {

            int a,b,c;

            scanf("%d%d%d",&a,&b,&c);

            dis[a- 1][b - 1] = c;

        }

        floyd();

        int Min = INF*200, flag = 0;

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

        {

            int sum = 0;

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

            {

                sum += dis[i][j] + dis[j][i];

            }

            if(sum < Min) flag = i, Min = sum;

        }

        int temp[200];

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

        {

            temp[i] = dis[flag][i] + dis[i][flag];

        }

        sort(temp,temp+n,greater<int>());

        for(int i = 0 ; i < m; i++)

            Min -= temp[i];

        printf("Case %d:\n",Case++);

        Min > INF ?

printf("No solution\n") : printf("%d\n",Min);

    }

    return 0;

}

秒客网

HLJOJ1015(多源最短路径失真)

相关文章