每日一题

从题目来看这就是个树啊
从题目来看这就是个树啊
从题目来看这就是个树啊
我真的好菜。。。看的好多人的题解才会&%！&%￥#……&
度为1的节点就是叶子节点
度为1的节点就是叶子节点
度为1的节点就是叶子节点
首先我们从 s 出发，那么我们不能让叶子节点走到 s 的话，我们现在有两种选择，设 u 是 s 的子节点 我们可以直接切断 u 到 s 的这条路径，或者我们进入这个子节点 切掉他的儿子到他的路，或者又进入下一层，。。。。。。一直重复当前的操作，很明显这就是个递归的过程。
无向图的存储一定要记住 * 2 啊 血淋淋的教训
无向图的存储一定要记住 * 2 啊 血淋淋的教训
无向图的存储一定要记住 * 2 啊 血淋淋的教训
另外叶子节点要单独判断 让他为无穷大
另外叶子节点要单独判断 让他为无穷大
另外叶子节点要单独判断 让他为无穷大

#include<bits/stdc++.h>
#define pr printf
#define sc scanf
#define fur(i,a,b) for(int i = a; i<= b ;i++)
#define fdr(i,a,b) for(int i = a; i>= b ;i--)
using namespace std;
typedef long long ll;
const int N = 100000 * 2 +10 ;
ll dp[N];
int head[N],nex[N],edge[N],ver[N],tot;
void add(int u,int v ,int w)
{
    ver[++tot] = v;
    edge[tot] = w;
    nex[tot] = head[u];
    head[u] = tot;
}
int d[N];
int n,m,s;
void dfs(int u,int fa)
{
    if(d[u] == 1 && u != s){
        dp[u] = 0x3f3f3f3f;
        return;
    }
    for(int i = head[u];i;i = nex[i])
    {
        int v = ver[i],w = edge[i];
        if(v != fa){
            dfs(v,u);
            dp[u] = dp[u] +min(1ll*w,dp[v]);
        }
    }
}
int main()
{
   // freopen("in.txt","r",stdin);
    scanf("%d %d %d",&n,&m,&s);
    for(int i = 1 ;i <= m;i++)
    {
        int u,v,w;
        scanf("%d %d %d",&u,&v,&w);
        add(u,v,w);
        add(v,u,w);
        ++d[u],++d[v];
    }
    dfs(s,0);
    printf("%lld\n",dp[s]);
    return 0;
}