题解 | Rinne Loves Edges

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using pil=pair<int,long long>;
int main() {
    ios::sync_with_stdio(0);cin.tie(0);
    int n,m,s;
    cin>>n>>m>>s;
    vector<vector<pil>> adj(n+1);
    for(int i=0;i<m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
    }
    auto dfs=[&](auto dfs,int cur,int fa,ll last)->ll{
        if(adj[cur].size()==1&&adj[cur][0].first==fa)
        {
            return adj[cur][0].second;
        }
        ll minn=0;
        for(const pil&next:adj[cur])
        {
            if(next.first==fa) continue;
            minn+=dfs(dfs,next.first,cur,next.second);
        }
        return min(last,minn);
    };
    cout<<dfs(dfs,s,0,LLONG_MAX);
}