題目：ddos
題目連結：https://ac.nowcoder.com/acm/problem/201607
題意：有n個節點，m條邊，構成一個拓撲圖（有向無環圖）。求以節點1為起點，以節點n為終點的路徑數對20010905取模的結果。
輸入：第一行：兩個整數n,m。
接下來m行：每行三個整數x,y,z，表示節點x與y可以單向連接配接(x到y), 耗時為z。
資料滿足：3 <= n <= 100000, 1 <= m <= 200000, 0 <= z <= 10 ^ (pi * e)
pi為圓周率，e為自然常數。
輸出：輸出節點1到節點n的路徑數對20010905取模的結果。
樣例輸入：
4 4
1 2 3
1 3 1
2 4 1
3 4 3
樣例輸出：
2
樣例解釋：有兩條路徑（1 – 2 - 4）， （1 – 3 - 4）。
題目分析：記憶化搜尋。
解題步驟：dp[i]的意義是節點i到n的路徑數。一個節點的dp值是它相鄰的節點的dp值之和，節點n的dp值為1。題目路徑數可能爆long long，注意取模。
建議讀一下原題，本題重點是對題意的了解，邊權給出的範圍有圓周率和自然常數也暗示着邊權沒有意義。
ac代碼：
#include<iostream>
#include<vector>
using namespace std;
const int n = 1e5 + 10, m = 2e5 + 10, mod = 20010905;
vector<int> v[n];
int n, m;
long long f[n];
long long dfs(int x){
if(f[x] != 0) return f[x];
for(int i = 0;i < v[x].size();i++){
f[x] += dfs(v[x][i]);
}
return f[x];
}
void solve(){
scanf("%d %d", &n, &m);
f[n] = 1;
while(m--){
int x, y, z;
scanf("%d %d %d", &x, &y, &z);
v[x].push_back(y);
dfs(1);
f[1] %= mod;
printf("%lld\n", f[1]);
int main(void){
solve();
return 0;
時間複雜度：o（n + m）。
空間複雜度：o（n）。