AT_abc441_d.[ABC441D] Paid Walk

普及-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

有一个有向图（不一定简单），图中有 $N$ 个顶点和 $M$ 条边，顶点的编号为顶点 $1, 2, \ldots, N$ 。第
$i$ 条 $(1\leq i\leq M)$ 边从顶点 $U_i$ 到顶点 $V_i$ ，代价为 $C_i$ 。此外，每个顶点的出度最多为 $4$ 。

查找所有满足以下条件的顶点 $v(1\leq v\leq N)$ ：

存在一条从顶点 $1$ 到顶点 $v$ 的路径，且同时满足以下两个条件：

它恰好遍历了 $L$ 条边。如果同一条边被多次遍历，则每次遍历都计算在内。

已遍历边的代价总和至少为 $S$ ，至多为 $T$ 。(如果同一条边被多次遍历，则每次遍历的代价都会加到总和中）。

::::info[什么是出度？]
顶点 $u$ 的出度指的是从顶点 $u$ 出发的边的数量。即使多条边指向同一个顶点，也会分别计算。
::::

输入内容由标准输入法提供，格式如下

$N$ $M$ $L$ $S$ $T\\$
$U_1$ $V_1$ $C_1\\$
$U_2$ $V_2$ $C_2\\$
$\vdots\\$
$U_M$ $V_M$ $C_M$

按升序输出满足条件的顶点，以空格分隔。
如果没有满足条件的顶点，则输出空行。

输入#1

5 8 3 80 100
1 2 20
1 3 70
2 1 30
2 5 10
3 2 10
3 4 30
3 5 20
5 1 70

输出#1

1 5

输入#3

2 5 3 1 100
1 1 1
2 2 100
1 2 1
1 2 1
1 2 100

输出#3

1 2

给定图如下左图所示。每条边的代价都显示在该边的起始顶点附近。

下面的条件成立：

对于从顶点 $1$ 到顶点 $1$ 的路径，考虑顶点 $1$ $\to$ 顶点 $2$ $\to$ 顶点 $5$ $\to$ 顶点 $1$ 。这恰好遍历了三条边，遍历边的成本总和为 $20+10+70=100$ ，因此满足条件。
从顶点 $1$ 到顶点 $2$ 没有满足条件的路径。顶点 $1$ $\to$ 顶点 $2$ $\to$ 顶点 $1$ $\to$ 顶点 $2$ 是一条恰好穿过三条边的路径，但是这条路径所经过的边的成本总和为 $20+30+20=70<80$ ，因此不满足条件。
从顶点 $1$ 到顶点 $3$ 没有满足条件的路径。一条正好穿过三条边的路径是：顶点 $1 $ $\to$ 顶点 $2$ $\to$ 顶点 $1$ $\to$ 顶点 $3$ ，但是这条路径所遍历的边的成本总和为 $20+30+70=120>100$ ，因此不满足条件。
从顶点 $1$ 到顶点 $4$ 没有满足条件的路径。
对于从顶点 $1$ 到顶点 $5$ 的路径，可以考虑顶点 $1$ $\to$ 顶点 $3$ $\to$ 顶点 $2$ $\to$ 顶点 $5$ 。这恰好遍历了三条边，且遍历边的成本总和为 $70+10+10=90$ ，因此满足条件。

因此输出 $1$ , $5$ 。请注意，您需要按升序输出满足条件的顶点。

如果没有满足条件的顶点，则输出空行。

图可能包含自环和多条边。
在本样例中，顶点 $1$ 和 $2$ 的出度分别为 $4$ 和 $1$ 。

输入解题思路，AI测评打分。不知道怎么写?