SHUXK 位于一个王国之中。这个王国由N个城市构成,城市之间连有双向的道路,通过每条道路都需要一定的时间 。SHUXK 发现这个王国有两个主要城市 A 和 B,这两个城市之间人员来往非常频繁,以致于经常会发生交通堵塞 。他想使用魔法来改善这个情况。他拥有一种“路径魔法”:一次选择一条从 A 城到 B 城的路径(可以经过一条 边多次,也可以经过自环),将这条路径上每条道路的通过时间减少T( T可以取任意非负实数)。SHUXK 可以使 用这种魔法任意多次,但是仍然有一些限制:
第一行包含五个正整数N,M,A,B,L分别表示城市的数量、道路的数量、 A 城和 B 城的编号以及 SHUXK 的路径魔法 限制的道路数量。 以下M行每行含三个正整数x,y,t表示城市x和城市t间连有一条道路,通过所需的时间为t( 1 ≤ t≤ 10000)。 N<=100,M<=500,L<=6
只有一行一个实数,表示 SHUXK 可以获得的最大的愉悦度。 当你 的答案与标准答案的绝对误差不超过10^-6时即视为正确。
5 5 1 5 3 1 2 2 1 3 2 2 4 2 3 4 2 4 5 3
0.428571