C++14(g++5.4) 解法, 执行用时: 154ms, 内存消耗: 11920K, 提交时间: 2019-11-28 16:31:21

#include<bits/stdc++.h>
using namespace std;

vector<int>R[100005];
vector<long long>W[100005];
long long DFS(int x,int pre)
{
	long long i,j,s=0;
	for(i=0;i<R[x].size();i++)
	{
		j=R[x][i];
		if(j==pre)continue;
		if(R[j].size()==1)s+=W[x][i];
		else s+=min(W[x][i],DFS(j,x));
	}
	return s;
}
int main()
{
	int i,j,k,N,M,S;
	scanf("%d%d%d",&N,&M,&S);
	while(M--)
	{
		scanf("%d%d%d",&i,&j,&k);
		R[i].push_back(j),W[i].push_back(k);
		R[j].push_back(i),W[j].push_back(k);
	}
	printf("%lld\n",DFS(S,0));
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 153ms, 内存消耗: 8680K, 提交时间: 2020-02-27 12:40:10

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<pair<ll,ll> >v[100010];
ll n,m,s,a,b,c,dp[100010];
void dfs(ll x,ll p)
{
	ll fg=0,w=0;
	for(auto i:v[x])
	{
		ll f=i.first,s=i.second;
		if(f==p) continue;
		dfs(f,x);
		fg=1,w+=min(dp[f],s);
	}
	if(fg) dp[x]=w;
}
int main()
{
	cin>>n>>m>>s;
	memset(dp,0x3f,sizeof dp);
	while(m--)
	{
		cin>>a>>b>>c;
		v[a].push_back({b,c}),v[b].push_back({a,c});
	}
	dfs(s,0);
	cout<<dp[s];
}

Python3 解法, 执行用时: 615ms, 内存消耗: 38112K, 提交时间: 2021-05-24 22:04:11

import math

n, m, s = map(int, input().split())
g = [[] for _ in range(n)]
for _ in range(m):
	u, v, w = map(int, input().split())
	g[u - 1].append((v - 1, w))
	g[v - 1].append((u - 1, w))

def dfs(u, p):
	res = 0
	c = 0
	for v, w in g[u]:
		if v == p: continue
		c += 1
		res += min(dfs(v, u), w)
	if c == 0: return math.inf
	return res

print(dfs(s - 1, -1))