题目描述

给定无向图，每条边在拥堵系数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、先取最短再求期望，不等于取平均边权的最短路。

本地修订与来源

本题为经授权补全的本地训练修订版，原始公开题面保留在采集档案；修订了：公开缩域到n≤10、m≤20，原源n≤200、m≤400不再冒称覆盖；去随机生成假定，任意合法权值适用。明确全图同a、先取最短再求期望，不等于取平均边权的最短路。。此处题意、范围和输出约定以本修订版为准，不冒称原站或官方原版。原题链接：https://ybt.ssoier.cn/problem_show.php?pid=1723。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共5个测试点，非原站或官方原始数据。总分100分。