Codeforces #374 721C. Journey

正文索引 [隐藏]

传送门:http://codeforces.com/problemset/problem/721/C

题目翻译

一个没有环N个点M条边的图,经过每条边需要时间。求在T的时间内,如何从1走到N,并且经过最多的点。输出方案。

题解

首先没有环,所以我们不用担心一条路径从自己有更新了自己。所以我们可以直接用DP推。 F[i][j] 已经经过了i个点,当前在点j的最小时间。 用M条边,更新F[i][x] -> F[i+1][x]

代码