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

· · 题解

香甜的黄油

弗洛伊德算法

#include<iostream>

#include<algorithm>

using namespace std;

int jl[5000][5000];//距离

int main()

  {

    int n,ns,p,c,a[8000]={0},qd,zd,qz;

    cin>>n>>p>>c;//输入牛的数量，牧场和边数

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

    {

    cin>>ns;

    a[ns]++;

    }

    for(int i=1;i<=p;i++)

    for(int j=1;j<=p;j++)

    if(i!=j) jl[i][j]=1e9;

    for(int i=1;i<=c;i++)

    {
        cin>>qd>>zd>>qz;

        jl[qd][zd]=qz;

        jl[zd][qd]=qz;//双向边
    }

    for(int k=1;k<=p;k++)

    for(int i=1;i<=p;i++)

    for(int j=1;j<=i;j++)

        if(jl[i][k]+jl[k][j]<jl[i][j])

        {
            jl[i][j]=jl[i][k]+jl[k][j];

            jl[j][i]=jl[i][k]+jl[k][j];//弗洛伊德算法

        }

        int minnn=1e9,sum=0;

        for(int i=1;i<=p;i++)

        {
            for(int j=1;j<=p;j++)

            {

                sum+=jl[i][j]*a[j];

            }

            if(sum<minnn) minnn=sum;//比较

            sum=0;

        }

        cout<<minnn;//输出

    return 0;

}