题解 P1828 【香甜的黄油 Sweet Butter】

shadowice1984 · 2017-09-25 13:36:59 · 题解

floyd优化~~~

楼下大佬说floyd会超时，果真如此；

然而勒，路径都是双向边！

所以从i到j的距离等于j到i的距离~；

然后，就砍了一半的枝。

就过了········

方便萌新，写一下floyd的原理。

从i到j有两种途径，直接从i到j（路径不存在耗时即为无穷）

或者从i到k再从k到i。

然后选较短的就行了。

ps：邻接矩阵存图。

上代码~

#include<stdio.h>
using namespace std;
int n;int p;int c;
int map[800][805];
int d[805][805];
int mark[805];
const int inf=9999999;
int res=inf;
int main()
{
    scanf("%d%d%d",&n,&p,&c);
    for(int i=0;i<p;i++)//手动memset
    {
        for(int j=0;j<p;j++)
        {
            if(i==j)
            {
                map[i][j]=0;//到自己的距离为0
                d[i][j]=0;
            }
            else
            {
                map[i][j]=inf;
                d[i][j]=inf;
            }
        }
    }
    for(int i=0;i<n;i++)
    {
        int t;
        scanf("%d",&t);
        mark[t-1]++;//从零开始的数组
    }
    for(int i=0;i<c;i++)
    {
        int u;int v;int val;
        scanf("%d%d%d",&u,&v,&val);
        map[u-1][v-1]=val;//从零开始的数组
        map[v-1][u-1]=val;
        d[u-1][v-1]=val;//初始化d为邻接矩阵
        d[v-1][u-1]=val;
    }
    for(int k=0;k<p;k++)//floyd三重循环
    {
        for(int i=0;i<p;i++)
        {
            for(int j=0;j<i;j++)//灵魂剪枝，双向边算一半图就好了
            {
                if(d[i][j]>d[i][k]+d[k][j])
                {
                    d[i][j]=d[i][k]+d[k][j];
                    d[j][i]=d[i][j];//更新另一半
                }
            }
        }
    }
    for(int i=0;i<p;i++)//扫一遍，寻找最短路径和
    {
        int sum=0;
        for(int j=0;j<p;j++)
        {
            sum+=d[i][j]*mark[j];//因为是路径和，所以用mark数组保存奶牛头数
        }
        if(res>sum)res=sum;
    }
    printf("%d",res);
    return 0;//拜拜程序~
}