题解 | #Rinne Loves Edges#

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

typedef long long ll;
const int len = 1e5 + 10;
vector<int>edge[2*len];//因为是无向图，所以长度是2*len
map<pair<int, int>, ll>dis;//用map来存变权，因为用二维数组可能会爆(没试过，不过1e10的数组一般开不下)
ll res[len];//res[len]表示每个节点为根节点向下建立的子树所需要付出的最小代价

void dfs(int x, int fa)
{
    if((int)edge[x].size() == 1 && fa != -1)
    {
        res[x] = dis[{x, fa}];
        return ;
    }
    //如果自身结点x的度为一，fa!=-1表示不是s结点，按照题目要求，这个节点是不能和s结点联通的
    //它和s结点间通过切断x和fa间的边来隔断
    /*但是不一定要割这条表，因为如果父节点也割断了与s的连接，而且边比现在x和fa的权值小就只需要割父节点
    和爷爷节点的连接
    */
    
    ll ans = 0;
    //ans用来记录x的所有子节点向下建成的子树要割的权值总和。
    for(int i = 0; i < (int)edge[x].size(); i++)
    {
        int y = edge[x][i];
        if(y == fa)
        {
            continue;
        }
        dfs(y, x);
        ans += res[y];
    }
    res[x] = min(dis[{x,fa}], ans);
    //在x和fa结点，以及x的所有子节点向下建成的子树要割的权值总和间取最小值。
    //这个是以x为父节点所需要付出的最小价值。
    return ;
}

int main()
{
    int n,m,s,u,v,w;
    cin >> n >> m >> s;
    //用vector数组存储所有的边，存的是无向图。
    for(int i = 0; i < m; i++)
    {
        cin >> u >> v >> w;
        edge[u].push_back(v);
        edge[v].push_back(u);
        dis[{u,v}] = w;
        dis[{v,u}] = w;
    }
    
    dis[{s, -1}] = 0x3f3f3f;
    //因为用的是dp，每次结果需要根据自身结点与父节点的值以及它的各个子节点的res来更新自身结点的res
    //而s和-1间没有权重，不可能取到，所以取得是0x3f3f3f(近似看做无穷大)
    dfs(s, -1);
    //深度优先搜索建图
    cout << res[s];
    //答案就是以s为根节点建立的子树付出的最小代价

    return 0;
}