分数: 400 点
问题陈述
有一个有向图(不一定简单) N 顶点和 M 边,其中顶点编号为顶点 1, 2, \ldots, N.
的
树的 i-th (1\leq i\leq M) 边从顶点出发 U_i 到顶点 V_i 含成本 C_i。
另外,每个顶点的出度最多为 4.
查找所有顶点 v (1\leq v\leq N) 满足以下条件:
存在从顶点开始的路径 1 到顶点 v 满足以下两个条件:
- 它准确地遍历 L 边缘。如果同一条边被遍历多次,则每次遍历都被计数。
- 遍历的边的成本总和至少为 S 最多 T。 (如果多次遍历同一条边,则每次将成本添加到总和中。)
什么是出度?
顶点的出度 u 指从顶点出去的边数 u。即使多条边到达同一顶点,它们也会单独计数。约束
- 1\leq N\leq 2\times 10^5
- 1\leq M\leq 2\times 10^5
- 1\leq L \leq 10
- 1\leq S\leq T \leq 10^9
- 1\leq U_i,V_i\leq N
- 1\leq C_i\leq 10^8
- 每个顶点的出度最多为 4.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
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
给定的图形如下左图所示。每条边的成本显示在该边的起始顶点附近。

这里,以下内容成立:
- 对于从顶点开始的路径 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 按此顺序。请注意,您需要按升序打印那些满足条件的顶点。
示例输入 2
10 1 1 1 100 2 3 1
示例输出 2
如果没有满足条件的顶点,则打印空行。
示例输入 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 和 2 是
分别为 4 和 1。