← 返回题目列表

Codeforces · 1307/G

G. 牛与锻炼

中文机器翻译题面 查看原题

农夫约翰痴迷于让贝西多锻炼!

贝西正在农场里吃草,农场由 $$$n$$$ 田地组成,并通过 $$$m$$$ 定向道路连接。每条路都需要一些时间 $$$w_i$$$ 才能穿过。她目前在 $$$1$$$ 场地,并将在当天结束时返回位于 $$$n$$$ 场地的家。

Farmer John 计划增加穿过某些道路所需的时间。他可以将穿过每条道路所需的时间增加一个非负值,但对于第 $$$i$$$ 个计划,增加的总时间不能超过 $$$x_i$$$。

确定每个 $$$q$$$ 独立计划从 $$$1$$$ 到 $$$n$$$ 的最短路径的最大值。

输入

第一行包含整数 $$$n$$$ 和 $$$m$$$ ($$$2 \le n \le 50$$$, $$$1 \le m \le n \cdot (n-1)$$$) — 分别是田地数量和道路数量。

以下 $$$m$$$ 行均包含 $$$3$$$ 整数、$$$u_i$$$、$$$v_i$$$ 和 $$$w_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$1 \le w_i \le 10^6$$$),表示有一条来自田野的道路$$$u_i$$$ 到 $$$v_i$$$ 场,需要 $$$w_i$$$ 时间穿过。

保证存在从字段 $$$1$$$ 到达字段 $$$n$$$ 的方法。保证图不包含自环或平行边。可能有一条从 $$$u$$$ 到 $$$v$$$ 的道路和从 $$$v$$$ 到 $$$u$$$ 的道路。

下一行包含一个整数 $$$q$$$ ($$$1 \le q \le 10^5$$$),即计划数量。

以下 $$$q$$$ 行中的每一行都包含一个整数 $$$x_i$$$,即查询 ($$$0 \le x_i \le 10^5$$$)。

输出

对于每个查询,如果总增量不超过 $$$x_i$$$,则输出 Farmer John 可以做出的最短路径的最大值。

如果您的答案的绝对或相对误差不超过 $$$10^{-6}$$$,则视为正确。

正式来说,让您的答案为 $$$a$$$,陪审团的答案为 $$$b$$$。当且仅当 $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$$$ 时,您的答案才会被接受。

示例

输入 #1

3 3
1 2 2
2 3 2
1 3 3
5
0
1
2
3
4

输出 #1

3.0000000000
4.0000000000
4.5000000000
5.0000000000
5.5000000000