#5747. 「CCO 2026」Waterloo Tag

标签: 传统 | 时间限制: 4000 ms | 内存限制: 512 MiB |

题目描述

译自 CCO 2026 Day1 T1「Asteroid Mining」。

Roger 和 Troy 正在滑铁卢大学玩捉迷藏。滑铁卢大学可以抽象为 $N$ 座建筑，它们之间由 $M$ 条人行道相连。第 $i$ 条人行道连接建筑 $a_i$ 和 $b_i$，长度为 $d_i$ 米。任意两座建筑之间最多只有一条人行道。这些人行道除了在建筑处相遇外互不相交（即你只能在建筑处从一条人行道换到另一条人行道），并且由于桥梁和隧道的存在，它们可能不在同一个平面上。从任意一座建筑出发，都可以通过人行道到达其他任何建筑。

Roger 从 $1$ 号建筑开始游戏，他的移动速度最高为 $v_1$ 米/秒。Roger 可以选择在建筑内停留，也可以在人行道的任意位置等待。Roger 会以最大化游戏持续时间的方式进行移动。

Troy 会选择一座建筑 $x$，并在该处释放一群学生。这些学生会沿着所有人行道以 $v_2$ 米/秒的速度向外扩散。当 Troy 的学生抓到 Roger 时，捉迷藏游戏结束。

对于每座可能的起始建筑 $x$，游戏将持续多长时间？

输入格式

第一行包含 $4$ 个由空格隔开的整数 $N, M, v_1, v_2$ $(2 \le N \le 2000; N-1 \le M \le 5000; 1 \le v_1, v_2 \le 100)$。

接下来 $M$ 行，每行包含 $3$ 个整数，其中第 $i$ 行包含整数 $a_i, b_i, d_i$ $(1 \le a_i < b_i \le N; 1 \le d_i \le 10000)$。

输出格式

输出 $N-1$ 行，其中第 $i$ 行表示：若 Troy 在建筑 $i+1$ 处释放学生，游戏持续的秒数。你必须以最简分数形式输出持续时间。

请注意，若一个整数 $q$ 除以整数 $d$ 的余数为零，则称 $d$ 是 $q$ 的约数。若整数 $z$ 同时是 $x$ 和 $y$ 的约数，则称 $z$ 是 $x$ 和 $y$ 的公约数。对于分数 $x/y$，若满足 $y$ 为正数且 $x$ 与 $y$ 没有大于 $1$ 的公约数，则称该分数为最简分数形式。

样例 1

输入

3 2 1 10
1 2 135
1 3 15

输出

15/1
5/3

图片下载失败URL：https://img.loj.ac.cn/2026/06/16/59409eb66f20f.svg

当 $x=2$ 时，Roger 应该走向建筑 $3$。$15$ 秒后，学生在建筑 $3$ 抓到了 Roger，游戏结束。

当 $x=3$ 时，Roger 应该向建筑 $2$ 方向移动。$5/3$ 秒后，学生在建筑 $2$ 和 $3$ 之间的人行道上抓到了 Roger，游戏结束。注意，此时 Roger 移动了 $1.666\dots$ 米，而学生移动了 $15 + 1.666\dots$ 米。

样例 2

输入

4 4 1 1
1 2 2
1 3 2
2 3 2
1 4 2

输出

4/1
4/1
5/1

图片下载失败URL：https://img.loj.ac.cn/2026/06/16/9e75b160d64f9.svg

当 $x=2$ 时，Roger 应该走向建筑 $4$。

当 $x=3$ 时，Roger 应该走向建筑 $4$。

当 $x=4$ 时，Roger 应该走向建筑 $2$ 和 $3$ 之间人行道的中点。

数据范围与提示

详细子任务附加限制及分值如下表所示。