推荐使用本链接访问，以获得更好的排版

题目

小w不会离散数学，所以她van的图论游戏是送分的

小w有一张n个点n-1条边的无向联通图,每个点编号为1~n,每条边都有一个长度
小w现在在点x上
她想知道从点x出发经过每个点至少一次，最少需要走多少路

输入&输出

第一行两个整数 n,x,代表点数,和小w所处的位置
第二到第n行,每行三个整数 u,v,w,表示u和v之间有一条长为w的道路

一个数表示答案

样例

输入

3 1
1 2 1
2 3 1

输出

2

说明

1 ≤ n ≤ 50000 , 1 ≤ w ≤ 2147483647

思路

n 个节点 n-1 条边的无向联通图实际上是 树

做法

从某点经过全部节点的路权和 = 总共的路权 * 2-该节点最长路的路权 以输入 为例

4 1
1 2 2
1 3 3
3 4 4

由于树的特殊性(联通 和 无环) 树上任意两个节点的路径只有一条，因此该路径的权值和可以用 BFS 来求

代码

#include<bits/stdc++.h>
#define endl '\n'
typedef long long ll;
using namespace std;
/*
2025/01/27
tag: 树, 最短路, 树上的TSP, BFS
*/



void solve() {
	// n 节点数量, n-1边的数量(n节点,n-1条边的无向联通图就是树)
	// x 起点
	int n,x;
	cin >> n >> x;
	// 邻接表
	vector<vector<pair<int,int>>> adj(n+1);
	// 总权值
	ll weigth_sum=0;
	for(int i=0;i<n-1;i++) {
		// 两个节点 权值
		int u,v,w;
		cin >> u >> v >>w;
		// 无向图, 两个端点都要更新
		adj[u].push_back({v,w});
		adj[v].push_back({u,w});
		weigth_sum+=w;
	}
	
	// BFS 计算最长路径
	
	// dist 用于表示该点离其他点的距离
	vector<ll> dist(n+1, -1);
	// 访问队列
	queue<int> q;
	// 现将起点如队
	q.push(x);
	// 起点到自身的距离是 0
	dist[x]=0;
	
	// 队列不为空
	while(!q.empty()){
		// 取出队首节点
		int u=q.front();
		q.pop();
		// 遍历节点 u 的邻接表
		for(int i=0;i<adj[u].size();i++) {
			int v = adj[u][i].first; // 编号
			int w = adj[u][i].second; // 权值
			// 节点 v 未访问
			if(dist[v]==-1) {
				// 更新距离
				dist[v] = dist[u]+w;
				// v 入队
				q.push(v);
			}
		}
	}
	
	// 寻找最长距离
	ll max_dist=0;
	for(int i=1;i<=n;i++) {
		max_dist=max(max_dist,dist[i]);
	}
	
	// 最短路径的路权和 = 全部路权*2-最长路的路权
	cout <<2*weigth_sum-max_dist<<endl;
}

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

	int t=1;
	//cin >> t;
	while(t--) solve();
	return 0;
}