思路:

多源BFS记录出从每个点出发,当前在哪个点,当前的距离是多少即可,最后在依次枚举每个点做起点判断即可

Code

#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
using PII=pair<int,int>;
const int N=110;
int n,w[N][N],cnt[N],dist[N][N]; //dist[i][j]表示i到j的最短路径
struct Q{
    int start,u,d;
};
void bfs(){
    memset(dist,0x3f,sizeof dist);
    queue<Q>q;
    for(int i=1;i<=n;i++){
        q.push({i,i,0});
        dist[i][i]=0;
    }
    while(!q.empty()){
        Q t=q.front();
        q.pop();
        int start=t.start,u=t.u,d=t.d;
        for(int i=1;i<=n;i++){
            if(dist[start][i]>d+w[u][i]){
                dist[start][i]=d+w[u][i];
                q.push({start,i,dist[start][i]});
            }
        }
    }
}
int main(){
    cin>>n;
    memset(w,0x3f,sizeof w);
    for(int i=1;i<=n;i++){
        cin>>cnt[i];
        int a,b;
        cin>>a>>b;
        w[a][i]=w[i][a]=1;
        w[b][i]=w[i][b]=1;
    }
    bfs();
    int res=2e9;
    for(int i=1;i<=n;i++){
        int sum=0;
        for(int j=1;j<=n;j++){
            sum+=dist[i][j]*cnt[j];
        }
        res=min(res,sum);
    }
    cout<<res<<endl;
    return 0;
}