题目链接：https://ac.nowcoder.com/acm/contest/370/F

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 131072K，其他语言262144K
64bit IO Format: %lld

题目描述 

Rinne  最近了解了如何快速维护可支持插入边删除边的图，并且高效的回答一下奇妙的询问。

她现在拿到了一个 n 个节点 m 条边的无向连通图，每条边有一个边权 wiwi

现在她想玩一个游戏：选取一个 “重要点” S，然后选择性删除一些边，使得原图中所有除 S 之外度为 1 的点都不能到达 S。

定义删除一条边的代价为这条边的边权，现在 Rinne 想知道完成这个游戏的最小的代价，这样她就能轻松到达 rk1 了！作为回报，她会让你的排名上升一定的数量。

 

输入描述:

第一行三个整数 N,M,S，意义如「题目描述」所述。

接下来 M 行，每行三个整数 u,v,w 代表点 u 到点 v 之间有一条长度为 w 的无向边。

输出描述:

一个整数表示答案。

示例1

输入

4 3 1 
1 2 1 
1 3 1 
1 4 1

输出

3

说明

需要使得点 2,3,4 不能到达点 1，显然只能删除所有的边，答案为 3

示例2

输入

4 3 1 
1 2 3 
2 3 1 
3 4 2

输出

1

说明

需要使得点 4 不能到达点 1，显然删除边 2↔32↔3是最优的。

备注:

2≤S≤N≤105,M=N−12≤S≤N≤105,M=N−1，保证答案在 C++ long long 范围内。
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstring> 
using namespace std;
typedef long long ll;
const int N=1e5+5;
struct node{
	int v;
	ll w;
	node(){}
	node(int vv,ll ww){
		v=vv;
		w=ww;
	}
};
bool vis[N];
ll dp[N];
vector<node>v[N];
const ll INF=1e16;
ll dfs(int u){
	ll ans=0;
	for(int i=0;i<v[u].size();i++){
		int t=v[u][i].v;
		ll w=v[u][i].w;
		if(vis[t]) continue;
		vis[t]=true;		
		ans+=min(dfs(t),w);		
	}	
	return dp[u]=ans?ans:INF;
}
int main(){
	int n,m,s;
	scanf("%d%d%d",&n,&m,&s);
	for(int i=1;i<=m;i++){
		int a,b;
		ll w;
		scanf("%d%d%lld",&a,&b,&w);
		v[a].push_back(node(b,w));
		v[b].push_back(node(a,w));
	}
    vis[s]=true;
	dfs(s);
	printf("%lld\n",dp[s]);
	return 0;
}