p1364 医院设置 题解

思路:floyd

很普通的思路。

先用floyd求出两个边之间的距离，然后乘以人数。

代码：

#include<iostream>
#include<cstring>
using namespace std;
const int inf=100000007;
int p[101],dis[101][101],sum;//dis类似邻接矩阵
int n,lch,rch;
int main()
{
    cin>>n;
    memset(dis,inf,sizeof(dis));//清为大数
    for(int i=1;i<=n;i++)
    {
        dis[i][i]=0;
        cin>>p[i];
        cin>>lch>>rch;
        if(lch>=0) dis[i][lch]=1;dis[lch][i]=1;//对于每一个点来说，从别的点走到这个点和从这个点走到别的点来说是不一样的
        if(rch>=0) dis[i][rch]=1;dis[rch][i]=1;
    }
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)//floyd三层暴力循环
            {
                if(dis[i][j]>dis[i][k]+dis[k][j]) dis[i][j]=dis[i][k]+dis[k][j];
            }
        }
    }
    int minn=inf;
    for(int i=1;i<=n;i++)//对于每一个点都要算一遍，
    {
        sum=0;
        for(int j=1;j<=n;j++)/遍历/每一个边
        {
            sum+=p[j]*dis[i][j];
        }
        if(minn>sum) minn=sum;更新最sum
    }
    cout<<minn<<endl;
    return 0;
}

完结撒花✿✿ヽ(°▽°)ノ✿