记忆化搜索

开始我还以为是一个最小生成树的题目，后面发现不是，他这里的边不起到作用，可以说是可有可无的，最后看来这就是一个深度优先搜索求到达终点可行边的数量

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
const int mod = 20010905;

struct node
{
    int v, next;
} e[maxn << 1];
int f[maxn], tot, h[maxn];

void add(int u, int v) //链式前向星加边
{
    e[++tot].v = v;
    e[tot].next = h[u];
    h[u] = tot;
}

int dfs(int x) //记忆化搜索
{
    if (f[x])
        return f[x];
    for (int i = h[x]; i; i = e[i].next) //依次遍历该点的邻接点
        f[x] = (f[x] + dfs(e[i].v)) % mod;
    return f[x];
}
int main()
{
    int u, v, w, n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; ++i)
    {
        scanf("%d%d%d", &u, &v, &w);
        add(u, v);
    }
    f[n] = 1; //把终点置为1，如果到达终点一次就加1，代表一种可行的路径
    printf("%d\n", dfs(1));
}