P10819 [EC Final 2020] City Brain

Pang 教授在首都 Grancel 的城市大脑项目工作。Grancel 的道路网络可以用一个无向图表示。最初，每条道路的限速为 $1$ 米每秒。Pang 教授可以花费 $1$ 美元将某条道路的限速提高 $1$ 米每秒。Pang 教授有 $k$ 美元。他可以在每条道路上花费任意非负整数金额。如果某条道路的限速为 $a$ 米每秒，则任何人通过这条道路需要 $1/a$ 秒的时间。 在 Pang 教授花费完他的资金后，Du 教授开始从城市 $s_1$ 前往城市 $t_1$，而 Wo 教授开始从城市 $s_2$ 前往城市 $t_2$。帮助 Pang 教授明智地花费他的资金，以最小化 Du 教授和 Wo 教授的最短旅行时间之和。保证 $s_1$ 和 $t_1$ 之间至少有一条路径连通，$s_2$ 和 $t_2$ 之间也至少有一条路径连通。

第一行包含三个整数 $n$、$m$、$k$ ($1\le n \le 5000$, $0\le m \le 5000$, $0\le k\le 10^9$)，用单个空格分隔，分别表示图中的顶点数、边数和 Pang 教授拥有的美元数。 接下来的 $m$ 行中，每行包含两个整数 $a$、$b$ ($1\le a, b\le n, a \neq b$)，用单个空格分隔，表示一条道路的两个端点。同一对城市之间可以有多条道路。 接下来的一行包含四个整数 $s_1$、$t_1$、$s_2$、$t_2$ ($1\le s_1, t_1, s_2, t_2\le n$)，用单个空格分隔，表示 Du 教授和 Wo 教授旅行的起点和终点。

输出一个小数，表示 Du 教授的旅行时间和 Wo 教授的旅行时间的最小和。如果其与标准答案的绝对误差或相对误差不超过 $10^{-9}$，则答案被视为正确。

（由 ChatGPT 4o 翻译）