题目描述

SHUXK 位于一个王国之中。这个王国由N个城市构成，城市之间连有双向的道路，通过每条道路都需要一定的时间 。SHUXK 发现这个王国有两个主要城市 A 和 B，这两个城市之间人员来往非常频繁，以致于经常会发生交通堵塞 。他想使用魔法来改善这个情况。他拥有一种“路径魔法”：一次选择一条从 A 城到 B 城的路径（可以经过一条 边多次，也可以经过自环），将这条路径上每条道路的通过时间减少T（ T可以取任意非负实数）。SHUXK 可以使 用这种魔法任意多次，但是仍然有一些限制：

1. 不能使得某一条道路的通过时间T ≤ 0，否则会违反时间法；
2. 由于使用一次魔法所需要的魔力与路径上的道路数量呈指数关系，所以 一次选择的路径上不能有超过??条道路。 想着自己是在为民造福， SHUXK 很高兴。他的愉悦度定义为每一次路径魔法的T值之和再除以 7。（为什么要除以  7？因为 SHUXK 很喜欢 142857 这个数）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

提示

没有写明提示

题目来源

没有写明来源