题解 | Rinne Loves Edges

#include<bits/stdc++.h>

using namespace std;

const int N = 1e5+5;

int n,m,s;
int fa[N];

vector< pair<int,int> >e[N];

inline int dfs(int x,int fa)
{
    int ans = 0;
    bool flag = false;
    for(auto i:e[x])
    {
        if(i.first == fa) continue;
        flag = true;
        ans += min(dfs(i.first, x), i.second);
    }
    if(!flag) return 0x3f3f3f3f;
    return ans;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        e[u].push_back({v,w});
        e[v].push_back({u,w});
    }
    cout<<dfs(s,0);
    return 0;
}