暴力出奇迹。

思路

首先预处理出 $len$，$len[i][j]$ 表示图中 $i$ 到 $j$ 的距离，使用记忆化搜索处理。每遍历到一个点就要把整张图遍历一次，时间复杂度为 $O(n^2)$。

最后我们再 $O(n^2)$ 地去枚举，求出将医院建在点 $i$ 处的距离和，对于每一个点的答案取最小值就是最终答案。

总复杂度为 $O(n^2)$。

AC Code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=105;
ll n,len[N][N],ans=LLONG_MAX;
struct node{
    ll val;
    vector<ll> vec;
}a[N];
bool flag[N];
void dfs(ll fa,ll x,ll dep){
    if(flag[x])
        return;
    flag[x]=1;
    len[fa][x]=dep*a[fa].val;
    for(auto i=a[x].vec.begin();i!=a[x].vec.end();i++)
        dfs(fa,*i,dep+1);
}
int main(){
    scanf("%lld",&n);
    for(ll i=1,u,v;i<=n;i++){
        scanf("%lld%lld%lld",&a[i].val,&u,&v);
        // 这里要记得特判u或v为0的情况，否则会出错
        if(u)
            a[i].vec.push_back(u),a[u].vec.push_back(i);
        if(v)
            a[i].vec.push_back(v),a[v].vec.push_back(i);
    }
    for(ll i=1;i<=n;i++){
        memset(flag,0,sizeof(flag));
        // 每求完一个点就重新初始化flag数组
        dfs(i,i,0);
    }
    for(ll i=1;i<=n;i++){
        ll cnt=0;
        for(ll j=1;j<=n;j++)
            cnt+=len[j][i]; //这里不能写成len[i][j]
        ans=min(ans,cnt);
    }
    printf("%lld",ans);
    return 0;
}