题目看上去感觉像是dijstra，但是不是最短路，而是在实践允许的范围内选择最多的点去走完从1到n的路，这个想到的是动态规划，以边为核心，一条边一条边的扫过，如果这条边对应的起点和终点连接上之后，对于从1到终点来说是有利的就加上那种，我还不是很理解，只是把标程看懂自己敲了一遍而已。
#include<iostream> using namespace std; #include<stack> const int inf = 0x3f3f3f;//特别大的数，记下来 const int maxn = 5005; int dp[maxn][maxn], pre[maxn][maxn]; //dp[i][j]表示经过i个点，从1到j，其中点的个数包括j struct edge { int u, v, w; }eg[maxn]; int n, m, t; stack<int>reu; int main() { while (cin >> n >> m >> t) { memset(dp, inf, sizeof(dp)); memset(pre, -1, sizeof(pre)); int i; for (i = 0; i < m; i++) cin >> eg[i].u >> eg[i].v >> eg[i].w; int j; int pos; dp[1][1] = 0;//从1到1必然是0 for (i = 2; i <= n; i++)//从2开始循环，到n个点 { for (j = 0; j < m; j++)//扫过每条边 { int u = eg[j].u; int v = eg[j].v; int w = eg[j].w; if (dp[i - 1][u] + w < dp[i][v])//关键的动态规划的过程 { dp[i][v] = dp[i - 1][u] + w; pre[i][v] = u;//表示经过i个点到达v之后，前一个点是u } } if (dp[i][n] <= t) pos = i;//更新一次答案 } cout << pos << endl; int ans = n; while (ans != -1) { reu.push(ans); ans = pre[pos--][ans];//所以pre是一个用来记录路线的数组 } while (!reu.empty()) { cout << reu.top() << " "; reu.pop(); } cout << endl; } return 0; }希望日后可以对dp有更深的理解！
