题解：AT_abc441_d [ABC441D] Paid Walk

· · 题解

前言

这次 ABC 切下了 ABCDE 喵，很满意的，于是来写几篇题解！

思路

看到这题 400 分，知道一定不能特别难，然后观察数据。

我们发现 1\le L\le 10，以及每个点的出度不超过 4，那么暴力枚举的话，最多需要枚举 4^{10} 次，也就是 1048576 次，复杂度完全可以接受。

我们可以考虑一个函数来 DFS。函数里尽量多传参，把走的边数以及一共的价值都作为参数传进去，如果走的边数达到了 L，判断价值是否合法。如果合法，记录答案。判断完毕后返回。

把走的边数以及一共的价值都作为参数传进去的好处是返回时就自动把加进去的减回来了，无需处理过多细节。

最后注意如果没有合法的也要输出换行。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node{
    int w,x;
};
vector<node>g[300005];
int N,M,L,S,T,a[300005];
void dfs(int x,int y,int z){
    if(y==L&&z>=S&&z<=T){a[x]=1;return;}
    if(y==L)return;
    for(int i=0;i<g[x].size();i++){
        dfs(g[x][i].w,y+1,z+g[x][i].x);
    }
}
signed main(){
    cin>>N>>M>>L>>S>>T;
    for(int i=0;i<M;i++){
        int u,v,c;
        cin>>u>>v>>c;
        g[u].push_back({v,c});
    }
    dfs(1,0,0);
    for(int i=1;i<=300000;i++){
        if(a[i]==1)cout<<i<<' ';
    }
    cout<<endl;
}