题意：一个n个点，m条边的无环无重边有向图，经过第i条路径需花费时间ti，要求你选一条从1到n的路径，使得经过的不同城市最多，并且总时间小于等于t。       题解：很简单的一道dp，考试的时候没想出来，一通乱搞，最后跑去A了D题。 dp[i][j]表示第i个点，已经经过了j个点的最小时间，按照拓扑序搞一搞即可。 1 #include<bits/stdc++.h> 2 #defin

传送门 题意：n个点m条边的有向无环图，每走一条边消耗一定时间，问从1走到n，消耗时间不超过T的情况下最多经过多少个点 题解：由于n，m范围不大所以对于这个DAG可以做的dp，定义f[i][j]表示走到i点，经过了j个点消耗时间的最小值，顺便开个pre数组记录一下转移路径。 说一下坑点，首先这个题卡空间，边权和f数组都不能是longlong。而且1不一定是DAG入度为0的点，也就是说1不一定