2020-07-10医院设置

题目：https://www.luogu.com.cn/problem/P1364

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<set>
using namespace std;
int read(){
    int x=0,f=1;
    char c = getchar();
    while(c<'0'||c>'9'){//符号位
        if(c=='-')
            f=-1;
        c = getchar();
    }
    while(c>='0'&&c<='9'){//数字
        x = x*10 + c -'0';
        c=getchar();
    }
    return x*f;
}


int a[101],g[101][101];

int main()
{
    /*read*/
    int n = read();
    
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            g[i][j]=1000000;
        }
    }
    for(int i=1;i<=n;i++)//读入、初始化
    {
        int l,r;
        g[i][i]=0;
        a[i] = read();
        l = read();
        r = read();
        if(l>0){
            g[i][l] = g[l][i] = 1;
        }
        if(r>0){
            g[i][r] = g[r][i] = 1;
        }
    }
    
    /*func*/
    for(int k=1;k<=n;k++)//用Floyed求任意两结点之间的最短路径
    {
        for(int i=1;i<=n;i++)
        {
            if(i!=k)
            {
                for(int j=1;j<=n;j++)
                {
                    if(i!=j&&k!=j&&(g[i][k]+g[k][j]<g[i][j]))
                        g[i][j]=g[i][k]+g[k][j];
                }
            }
        }
    }
    
    int min=0x7fffffff;
    int total;
    for(int i=1;i<=n;i++)//穷举医院建在N个结点，找出最短距离
    {
        total=0;
        for(int j=1;j<=n;j++){
            total+=g[i][j]*a[j];
        }
        if(total<min){
            min=total;
        }
    }
    printf("%d",min);
    return 0;
}
/*
5
13 2 3
4 0 0
12 4 5
20 0 0
40 0 0
*/