题目描述

给定无向图，每条边在拥堵系数a时的时间为a·x+(1−a)·y。全图共享一个a，a在[0,1]均匀分布。每天根据实际a选择S到T最短路，求该最短路长度的期望，即积分∫0^1 dist_a(S,T) da。

本题为一本通1723的公开本地训练修订版。

输入

首行n m S T，1≤n≤10，0≤m≤20，1≤S,T≤n。随后m行u v x y，端点不同、允许重边，1≤x,y≤10^7。保证S到T有路；S=T时允许空路径。

输出

输出一个有限实数，绝对误差≤10^-6。建议保留10位小数。

输入样例

2 1 1 2
1 2 3 2

输出样例

2.5

修订说明

公开缩域到n≤10、m≤20，原源n≤200、m≤400不再冒称覆盖；去随机生成假定，任意合法权值适用。明确全图同a、先取最短再求期望，不等于取平均边权的最短路。