题意：
给出一个图，问从点1到n，在总时间为T的情况下最多能经过多少城市？
要点：
一看就知道是DAG里的DP，直接递推比较难写，用记忆化搜索比较方便，基本思路就是用dp[i][j]存储从i开始经过j个城市所需最少时间，最后找出时间小于等于T的j的最大值即可。
#include<iostream>
#include<cstring>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn = 5050;
int n, m, T;
typedef pair<int, int> Pair;
int dp[maxn][maxn], nex[maxn][maxn];
vector<Pair> 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;
}