40pts

WA# 345

打的bfs

#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <cmath>
#include <bits/stdc++.h>
#define mp(a,b) make_pair(a,b)
#define PII pair<int,int>
#define unll unsigned ll
#define ll long long
using namespace std;
const int N=105,INF=INT_MAX;
int n,w[N],ans=INF;
vector<int> vc[N];
bool vis[N];
int dis[N],sum;
queue<int> q;
void Clear()
{
	sum=0;
	memset(vis,0,sizeof(vis));
	memset(dis,0,sizeof(dis));
	while(!q.empty()) q.pop();
}
int bfs(int step)
{
	vis[step]=1;
	q.push(step);
	int u;
	while(!q.empty())
	{
		u=q.front();
		q.pop();
		for(auto v:vc[u])
		{
			if(vis[v]) continue;
			vis[v]=1;
			dis[v]=dis[u]+1;
			sum+=dis[v]*w[v];
			q.push(v);
		}
	}
	ans=min(ans,sum);
}
int main()
{
	scanf("%d",&n);
	int u,v;
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d%d",&w[i],&u,&v);
		vc[i].push_back(u);
		vc[u].push_back(i);
		vc[i].push_back(v);
		vc[v].push_back(i);
	}
	for(int i=1;i<=n;i++)
	{
		Clear();
		bfs(i);
	}
	printf("%d",ans);
	return 0;
}