← 返回题目列表

AtCoder · abc441_d

G. 付费步行

中文机器翻译题面 查看原题

分数: 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。