3520. [POJ 3621]观光奶牛

【题目描述】

农夫约翰已决定通过带他们参观大城市来奖励他们的辛苦工作！奶牛必须决定如何最好地度过他们的空闲时间。

幸运的是，他们有一个详细的城市地图，显示L（2≤L≤1000）个主要地标（方便编号为1 .. L）和P（2≤P≤5000）条单向奶牛路径。农夫约翰将把奶牛带到他们选择的起始地标，从那里他们将沿着奶牛路径走到一系列其他地标，最后回到他们的起始地标，农民约翰将把他们带回农场。因为城市中的空间非常宝贵，所以奶牛路径非常狭窄，因此沿着每个奶牛路径行进仅允许在一个固定方向上行进。

虽然奶牛可能会在城市中花费尽可能多的时间，但他们确实也很容易感到厌倦。虽然访问每个新地标很有趣，但在它们之间行走需要时间。奶牛知道每个地标i的确切有趣值Fi（1≤Fi≤1000），也知道第i条奶牛路径将地标L1i连接到L2i（方向L1i - > L2i）并且需要时间Ti（1≤Ti≤1000）来遍历。

为了尽可能享受最佳休息日，奶牛希望最大限度地提高每次旅行单位时间的平均乐趣价值。当然，这些地标在他们第一次参观时才很有趣; 奶牛可能不止一次穿过地标，但此时奶牛就感受不到地标的有趣价值。此外，农夫约翰要求奶牛至少访问两个标志性建筑，以便他们在休息期间可以得到一些锻炼。

请你帮助奶牛找到每单位时间可以达到的最大乐趣值。

【输入格式】

第一行，两个整数L,P；

第2到L+1行，第i+1行有一个整数Fi；

第L+2行到L+P+1行，第L+i+1描述了奶牛路径L1i,L2i,Ti。

【输出格式】

一行，一个数表示最大乐趣值，保留两位小数。

【样例输入】

5 7
30
10
10
5
10
1 2 3
2 3 2
3 4 5
3 5 2
4 5 5
5 1 3
5 2 2

【样例输出】

6.00

提示

USACO 2007 12月 Gold