题意：

给出一个图，问从点1到n，在总时间为T的情况下最多能经过多少城市？

要点：

一看就知道是DAG里的DP，直接递推比较难写，用记忆化搜索比较方便，基本思路就是用dp[i][j]存储从i开始经过j个城市所需最少时间，最后找出时间小于等于T的j的最大值即可。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         using namespace std;const int maxn = 5050;int n, m, T;typedef pair
         
           Pair;int dp[maxn][maxn], nex[maxn][maxn];vector
          
            g[maxn];bool vis[maxn];void dfs(int u){ vis[u] = true; for (int i = 0; i < g[u].size(); i++) { int v = g[u][i].first; int t = g[u][i].second; if (!vis[v]) dfs(v); for (int j = 2; j <= n; j++) if (dp[u][j] > dp[v][j - 1] + t) { dp[u][j] = dp[v][j - 1] + t; nex[u][j] = v; } }}int main(){ int i, j; scanf("%d%d%d", &n, &m,&T); for (i = 1; i <= m; i++) { int u, v,t; scanf("%d%d%d", &u, &v, &t); g[u].push_back(make_pair(v, t)); } memset(dp, 0x3f3f3f3f, sizeof(dp)); dp[n][1] = 0; memset(nex, -1, sizeof(nex)); dfs(1); for (int i = n; i >= 1; i--) { if (dp[1][i] <= T) { printf("%d\n", i); for (int j = 1; j != -1; j = nex[j][i], i--) printf("%d ", j); break; } } return 0;}