#include<bits/stdc++.h>
using namespace std;
int r[1145],g[200][200],n;
int main()
{
    cin>>n;
    memset(g,0x3f,sizeof(g));
    for(int i=1;i<=n;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        r[i]=a;
        if(b!=0)g[i][b]=g[b][i]=1;
        if(c!=0)g[i][c]=g[c][i]=1;
    }
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
    int ans=0x7fffffff;
    for(int i=1;i<=n;i++)
    {
        int sum=0;
        for(int j=1;j<=n;j++)
            if(i!=j){sum+=r[j]*g[i][j];}
        ans=min(ans,sum);
    }
    cout<<ans;
    return 0;
}

这题 $n$ 小得离谱，估计套 Floyd 都能过（乐

但咱还是有追求的人。

由于是边权为 $1$ 的图，跑一次 BFS 求可以 $O(n+m)=O(n)$ 的求出单源最短路，跑 $n$ 次即可。

一个显而易见的剪枝就是在求最短路的同时累加路程和，若当前路程和已经超过了之前的最短路程和，则直接返回。

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

int tot = -1;
int head[105], nxt[205], to[205];

int n, ans = 1e9;
int w[105], d[105][105];

void add_edge(int x, int y) {
	to[++tot] = y;
	nxt[tot] = head[x];
	head[x] = tot;
}

void bfs(int x) {
	int sum = 0;
	queue<int> q;
	memset(d[x], 0, sizeof d[x]);
	d[x][x] = 0;
	q.emplace(x);
	while (!q.empty()) {
		int cur = q.front();
		q.pop();

		for (int i = head[cur]; ~i; i = nxt[i]) {
			int y = to[i];
			if (d[x][y] || x == y) continue;
			d[x][y] = d[x][cur] + 1;
			sum += d[x][y] * w[y];
			if (sum > ans) return; // 剪枝
			q.push(y);
		}
	}
	ans = sum;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);

	cin >> n;
	memset(head, -1, sizeof head);
	for (int i = 1; i <= n; ++i) {
		int u, v;
		cin >> w[i] >> u >> v;
		if (u) add_edge(i, u), add_edge(u, i);
		if (v) add_edge(i, v), add_edge(v, i);
	}
	for (int i = 1; i <= n; ++i) bfs(i);
	cout << ans << endl;

	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000000000;
int n,ans=maxn,s[110];
struct Node{
    int left,right,father,value;
}t[110];
int c(int x,int d){
    if(!x||s[x]) return 0;
    s[x]=1;
    return c(t[x].left,d+1)+c(t[x].right,d+1)+c(t[x].father,d+1)+t[x].value*d;
}
int main(){
	cin >> n;
	for(int i=1;i<=n;i++) cin >> t[i].value >> t[i].left >> t[i].right;
	for(int i=1;i<=n;i++){
        t[t[i].left].father=i;
        t[t[i].right].father=i;
    }
    for(int i=1;i<=n;i++){
    	memset(s,0,sizeof(s));
    	ans=min(ans,c(i,0));
	}
	cout << ans;
	return 0;
}