NC 201607 DP

题意

传送门 NC 201607

题解

题意其实是求节点 $1$ 到节点 $n$ 的路径数…

$DAG$ 用动态规划求解，$dp[i]$ 代表节点 $i$ 到节点 $n$ 的路径数，转移方程为

$$dp[i]=\sum _{e(i,j)\in E}dp[j]$$

#include <bits/stdc++.h> using namespace std; #define maxn 100005 const int mod = 20010905; int n, m, dp[maxn]; vector<int> G[maxn]; int rec(int v){ if(dp[v] != -1) return dp[v]; int res = 0; for (int i = 0; i < G[v].size();i++){ res = (res + rec(G[v][i])) % mod; } return dp[v] = res; } int main() { scanf("%d%d", &n, &m); for (int i = 0; i < m; i++) { int x, y, z; scanf("%d%d%d", &x, &y, &z); G[x].push_back(y); } memset(dp, -1, sizeof(dp)); dp[n] = 1; printf("%d\n", rec(1)); return 0; }