1000ms

Difficulty: 5

所属公司 : 京东

时间 :2024年8月17日

算法与标签>动态规划

会员或题库专享

请先，开通会员或购买题库京东机考编程题库，可解锁完整内容。

购买京东机考编程题库开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（京东机考编程题库），可解锁完整内容。

购买题库开通会员

思路：动态规划

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

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

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

代码

题目描述

NN也是要回家过年的呢。

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