Round #2022/12/10

问题 D:城市大脑

题目描述

杜老师正在编写杭州城市大脑智能引擎。杭州的道路可以被抽象成为一幅无向图。每条路的初始速度都是 \(1\ m/s\)。杜老师可以使用 \(1\) 块钱让任意一条路的速度提升 \(1\ m/s\)。如果一条路的速度为 \(a\ m/s\)，那么我们需要 \(1/a\) \(s\)才能通过这条道路。初始杜老师有 k 块钱，杜老师要把这 k 块钱花在升级这些道路上。 现在有两位选手，一位要从 \(s_1\) 走到 \(t_1\)，一位要从 \(s_2\) 走到 \(t_2\)，请问杜老师要怎么花钱，使得两位选手花费的总时间最少？当杜老师花完钱之后，两位选手都会走花费时间最少的路。杜老师花在每条道路上的钱都必须是非负整数。

输入格式

第一行三个整数 \(n,m,k\) 分别表示点数、边数以及杜老师初始有多少钱。

接下来 \(m\) 行，每行两个正整数 a,b 表示边（可以有重边）。

接下来一行四个整数 \(s_1,t_1,s_2,t_2\)。数据保证 \(s_1,t_1\)、\(s_2,t_2\) 连通。

输出格式

一行一个数表示答案。相对误差或绝对误差在 \(10^{-9}\) 内即为正确。

样例输入#1

6 5 1
1 2
3 2
2 4
4 5
4 6
1 5 3 6

样例输出#1

5.000000000000

样例输入#2

1 0 100
1 1 1 1

样例输出#2

0.000000000000

样例输入#3

4 2 3
1 2
3 4
1 2 3 4

样例输出#3

0.833333333333

提示

对于 \(20\%\) 的数据，\(n,m \leq 10,k\leq 10\)；

对于 \(50\%\) 的数据，\(n,m \leq 10^3,k\leq 10^9\)。

对于 \(100\%\) 的数据，\(n,m \leq 5 \cdot 10^3,k\leq 10^9\)。

题解