交通

【题目描述】

提到$Z$国首都$B$市，人们的第一印象往往是拥堵的交通。为了简化问题，我们用一张无向图简单表示$B$市的交通路网，并假设整个$B$市的拥堵系数是一个$[0,1]$之间的常数$a$。对于每条路有个最拥堵时经过所需要的时间$x_i$和一个完全空闲时经过所需要的时间 $y_i$（不要问我为什么$x_i$ 可能小于$y_i$ ）。在拥堵系数为a的情况下，所需要的时间就是$ax_i+(1-a)y_i$ 。 $C$先生每天要从$S$地开车到$T$地。假设每天的拥堵系数在$[0,1]$之间均匀随机，试求期望的情况下从$S$到$T$的最短路。

【输入】

第一行四个数$n, m, S, T$。分别表示$B$市交通路网中的顶点个数，双向边的个数，起点，终点。点从$1$开始编号。 接下来$m$行，每行$4$个数$u,v,x,y$。表示存在一条$u$到$v$，系数分别为$x$和$y$的边。 数据保证$S$到$T$存在路径。保证图上没有自环，但是可能有重边。

【输出】

一行一个实数，表示期望最短路径。

【输入样例】

2 1 1 2
1 2 3 2

【输出样例】

2.5

【提示】

【样例输入2】

5 10 1 5
1 2 1 1
1 2 8 3
2 3 2 5
2 3 8 8
3 4 8 10
3 4 7 10
4 5 6 7
4 5 6 6
3 1 4 6
5 3 8 9

【样例输出2】

13.0

【数据规模】 对于30%的数据，满足$n≤10，m≤20$； 对于100%的数据，满足$n≤200，m≤400，1≤x,y≤10^7$。并且所有的$x,y$均在其范围内随机生成。

5 10 1 5\n1 2 1 1\n1 2 8 3\n2 3 2 5\n2 3 8 8\n3 4 8 10\n3 4 7 10\n4 5 6 7\n4 5 6 6\n3 1 4 6\n5 3 8 9

13.0