自创第一题
题目背景
最好的朋友在身边，最爱的人就在对面.
自爱情公寓拆迁已经过去十多年……
多年过后，曾经爱情公寓的每个人都成为了自己想成为的样子，一菲成为了著作等身的大教授兼弹一闪道馆馆主，小贤主持的新《你的太阳我的心》大火，咖喱酱成为了娱乐圈配音界的扛把子，子乔和美嘉把事业做大了，成为了人生赢家，海棠成为了一代文豪，大力在火星上研究水稻，张伟则跟随大力成为了火星上有名的大律师。这一天，海棠邀请朋友们来参加掘地重工举办的世界博览会，就这样，大家再一次重聚，踏上了世博会之旅……
题目描述
这次博览会一共有(n)个展厅，编号从(1)到(n)，且这些展厅是由单向道路连接的，掘地重工的工作人员们对这次博览会的路线进行了精心的设计，使得这次博览会的展厅之间不存在循环路线。
起初，小伙伴们在(1)号展厅，这次旅行的终点在(n)号展览厅---爱情公寓厅，这是掘地重工给爱情公寓的小伙伴们专门准备的礼物。因为他们想要尽快到达(n)号厅而又想尽量多的参观别的展厅，所以他们想在(t)个时间单位内到达(n)号厅。
假设参观展厅不需要花费时间，现在你的任务就是帮助他们在不超过(t)的时间内确定从(1)号展厅到(n)号展厅的旅程中最多可以参观多少个展厅。保证至少有一条从(1)号展厅到(n)号展厅的路线，并保证这条道路小伙伴们将花费不超过(t)个时间单位通过。
输入格式
第一行三个整数(n, m, t)，分别表示展厅的数量、展厅之间的道路数量以及时间限制。
接下来(m)行，每行三个整数(x,y,w)，表示从(x)号展厅到(y)号展厅有一条花费时间(w)的路线
输出格式
第一行一个整数(ans)，表示最多可以参观的展厅数量。
第二行(ans)个整数，按访问顺序输出路径（即每个访问到的点）
数据范围
对于(30%)的数据满足：(2≤n≤10),(1≤m≤10)
对于(100%)的数据满足：(2≤n≤5000,1≤m≤5000,t≤10^9,1≤w≤10^9)
(256MB)
注意
绝对良心题吧嘻嘻(qwq)
小清新简单题，用来休闲
solution
一句话题意
有一个(n)个点(m)条边的有向无环图，求从(1)到(n)总路径长度不超过(t)，且经过点最多的路径。
题解
拓扑排序+(DP)
说实话其实不用给部分分……
很显然，题目中给出的图是一个(DAG)(有向无环图)
因为(n)和(m)只有(5000)，所以我们可以大胆地写一个(O(nm))的算法。
因为要求最短路径，且图中无环，所以我们可以大胆地用(DP)来做
用一个二维数组(f[i][j])表示从(1)号点到(i)号点经过(j)个点的最短路径（初始化(inf)），最后只要从大到小判断第一个(f[n][i]le t)的(i)即可，同时，为了保证每个点都是最小值，(DP)要按照拓扑序的顺序(而不是节点序)，因为是(DAG)嘛~
转移：(f[x][j] = min(f[x][j], f[x][j - 1]+e[i].val))((i)是(x)的连边，(j=[2)~(n]))
再一个问题就是记录路径了，我们可以在(DP)过程中用一个类似于(f)数组的(pre)数组，(pre[i][j])表示从(1)走到(i)，经过了(j)个点的上一个节点的编号，输出的时候可以用(stack)记录，也可以直接回溯
代码
#include <stack>
#include <queue>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int A = 5e3 + 11;
const int INF = 0x3f3f3f3f;
inline int read() {
char c = getchar(); int x = 0, f = 1;
for ( ; !isdigit(c); c = getchar()) if (c == '-') f = -1;
for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return x * f;
}
int n, m, d, cnt, head[A];
struct node { int to, nxt, val; } e[A];
int f[A][A], pre[A][A], rdu[A], mx;;
vector <int> s;
stack <int> path;
inline void add(int from, int to, int val) {
e[cnt].to = to;
e[cnt].val = val;
e[cnt].nxt = head[from];
head[from] = cnt++;
}
void topo() { //拓扑排序
queue <int> q;
for (int i = 1; i <= n; i++) if (rdu[i] == 0) q.push(i);
while (!q.empty()) {
int x = q.front();
q.pop();
s.push_back(x);
for (int i = head[x]; i != -1; i = e[i].nxt)
if ((--rdu[e[i].to]) == 0) q.push(e[i].to);
}
}
signed main() {
freopen("5.in", "r", stdin);
freopen("5.out", "w", stdout);
memset(f, INF, sizeof(f));
memset(pre, -1, sizeof(pre));
memset(head, -1, sizeof(head));
n = read(), m = read(), d = read();
for (int i = 1, x, y, z; i <= m; i++) {
x = read(), y = read(), z = read();
add(x, y, z);
rdu[y]++;
}
topo();
f[1][1] = 0;
for (int k = 0; k < s.size(); k++) {
int x = s[k];
for (int i = head[x]; i != -1; i = e[i].nxt)
for (int j = 2; j <= n; j++)
if (f[x][j - 1] + e[i].val < f[e[i].to][j]) {
f[e[i].to][j] = f[x][j - 1] + e[i].val;
pre[e[i].to][j] = x;
}
}
for (int i = n; i >= 1; i--)
if (f[n][i] <= d) {
mx = i;
break;
}
cout << mx << '
';
int pos = n, dep = mx;
while (pos != -1) {
path.push(pos);
pos = pre[pos][dep];
dep--;
}
while (!path.empty()) {
cout << path.top() << ' ';
path.pop();
}
cout << '
';
return 0;
}