题目描述

NN也是要回家过年的呢。

NN所在的国家有 n 座城市，m 条有向道路，第 i 条道路由城市$u_i$通往城市$v_i$，通行费为 $w_i$。

思路：动态规划

定义$dp[i][s]$表示到点$i$且花费为$s$的方案有多少。

那么对于通向点$i$的点集$v∈{V}$，有$dp[i][s+w_{v->i}]+=dp[v][s]$

最终答案为$dp[n][a]$

代码