CF1307G Cow and Exercise

Farmer John 痴迷于让 Bessie 多锻炼！ Bessie 正在农场上吃草，农场由 $n$ 个牧场组成，通过 $m$ 条有向道路连接。每条道路需要 $w_i$ 时间通过。她现在在第 $1$ 个牧场，最终会回到她的家——第 $n$ 个牧场。 Farmer John 计划增加某些道路的通过时间。他可以将每条道路的通过时间增加一个非负数，但所有道路的总增加量不能超过第 $i$ 个计划中的 $x_i$。 对于每个独立的计划，请你计算 Farmer John 能让从 $1$ 号牧场到 $n$ 号牧场的最短路径最长能变为多少。

第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 50$，$1 \le m \le n \cdot (n-1)$），分别表示牧场的数量和道路的数量。 接下来的 $m$ 行，每行包含三个整数 $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$，表示第 $i$ 个计划允许的总增加量（$0 \le x_i \le 10^5$）。

对于每个计划，输出 Farmer John 能让最短路径最长变为多少。 如果你的答案的绝对误差或相对误差不超过 $10^{-6}$，则视为正确。 形式化地说，设你的答案为 $a$，标准答案为 $b$，当且仅当 $\frac{|a - b|}{\max(1, |b|)} \le 10^{-6}$ 时，你的答案被接受。

由 ChatGPT 4.1 翻译