Rinne Loves Edges

搜索时上一步的（以前的）东西可以通过参数带到下一步

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int const M=1e5+7;
int const N=1e5+7;
ll const INF=0x7fffffffffffffff;
int n,m,s;
struct node{
    int a,len,next;
}e[M<<1];
int head[N],cnt;
void add(int x,int y,int len){
    e[++cnt].a =y;
    e[cnt].len =len;
    e[cnt].next =head[x];
    head[x]=cnt;
}
int vis[N];
ll f[N];   //f[i]表示s和以i为根子树的叶子断开的最小代价 
void dfs(int s,ll len){
    vis[s]=1;
    ll z=0,fg=0;
    for(int i=head[s];i!=-1;i=e[i].next){
        if(vis[e[i].a]) continue;
        vis[e[i].a]=1;
        dfs(e[i].a,e[i].len );
        z+=f[e[i].a];
        fg=1;
    }
    if(fg) f[s]=min(z,len);
    else f[s]=len;
}
int main(){
    cin >> n >> m >> s;
    memset(head,-1,sizeof head);
    memset(e,-1,sizeof e);
    //memset(f,0x7f,sizeof f);
    for(int i=1;i<=m;++i){
        int a,b,c;
        cin >> a >> b >> c;
        add(a,b,c);add(b,a,c);
    }
    dfs(s,INF);
    cout << f[s];
    return 0;
}