Cow and Exercise
Contest: Codeforces Round 621 (Div. 1 + Div. 2)
Difficulty rating: 3100
Tags: flows, graphs, shortest paths

Farmer John is obsessed with making Bessie exercise more!

Bessie is out grazing on the farm, which consists of $$$n$$$ fields connected by $$$m$$$ directed roads. Each road takes some time $$$w_i$$$ to cross. She is currently at field $$$1$$$ and will return to her home at field $$$n$$$ at the end of the day.

Farmer John has plans to increase the time it takes to cross certain roads. He can increase the time it takes to cross each road by a nonnegative amount, but the total increase cannot exceed $$$x_i$$$ for the $$$i$$$-th plan.

Determine the maximum he can make the shortest path from $$$1$$$ to $$$n$$$ for each of the $$$q$$$ independent plans.

Input format:
The first line contains integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 50$$$, $$$1 \le m \le n \cdot (n-1)$$$) — the number of fields and number of roads, respectively.

Each of the following $$$m$$$ lines contains $$$3$$$ integers, $$$u_i$$$, $$$v_i$$$, and $$$w_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$1 \le w_i \le 10^6$$$), meaning there is an road from field $$$u_i$$$ to field $$$v_i$$$ that takes $$$w_i$$$ time to cross.

It is guaranteed that there exists a way to get to field $$$n$$$ from field $$$1$$$. It is guaranteed that the graph does not contain self-loops or parallel edges. It is possible to have a road from $$$u$$$ to $$$v$$$ and a road from $$$v$$$ to $$$u$$$.

The next line contains a single integer $$$q$$$ ($$$1 \le q \le 10^5$$$), the number of plans.

Each of the following $$$q$$$ lines contains a single integer $$$x_i$$$, the query ($$$0 \le x_i \le 10^5$$$).

Output format:
For each query, output the maximum Farmer John can make the shortest path if the total increase does not exceed $$$x_i$$$.

Your answer is considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$.

Formally, let your answer be $$$a$$$, and the jury's answer be $$$b$$$. Your answer is accepted if and only if $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Example input:
3 3
1 2 2
2 3 2
1 3 3
5
0
1
2
3
4

Example output:
3.0000000000
4.0000000000
4.5000000000
5.0000000000
5.5000000000

Editorial:
This problem can be formulated as a linear program, and looks like the LP dual of min-cost flow.
LP formulation of min-cost flow (see for example here: https://imada.sdu.dk/%7Ejbj/DM85/mincostnew.pdf):
$$$x_{vw}$$$ is flow on edge $$$(v,w)$$$
$$$c_{vw}$$$ is cost on edge $$$(v,w)$$$
$$$u_{vw}$$$ is capacity on edge $$$(v,w)$$$
$$$b_v$$$ is demand at vertex $$$v$$$ (flow in minus flow out)
Find $$$\min{\Sigma_{vw}c_{vw}x_{vw}}$$$ subject to $$$$$$\Sigma_{(v,w)\in E}(x_{wv}-x_{vw})=b_v$$$$$$ for $$$v\in V$$$
(Hopefully the signs are right.)
$$$$$$0\le x_{vw} \le u_{vw}$$$$$$ for $$$(v,w)\in E$$$
The LP Dual is
$$$$$$\max{\Sigma{b_vy_v}-\Sigma{u_{vw}z_{vw}}}$$$$$$ subject to $$$$$$y_w\le y_v+c_{vw}+z_{vw}$$$$$$ $$$$$$z_{vw}\ge 0$$$$$$ for all $$$(v,w)\in E$$$
This is exactly what we need, except the objective function is a bit messy. Letting $$$b_{src}=-F$$$, $$$b_{snk}=F$$$, $$$b_v=0$$$ for other $$$v$$$, $$$D=y_{snk}-y_{src}$$$, $$$C=\Sigma{vw}{u_{vw}z_{vw}}$$$, the objective becomes
$$$$$$\max{FD-C}$$$$$$
We have the unweighted case, so assign capacities (cost in original problem) $$$u_{vw}=1$$$ for all edges.
We can interpret $$$y_v$$$ as distance from $$$src$$$ and $$$z_{vw}$$$ as the amount added to edge edge to it.
The set of all valid assignments to the variables form a convex polytope. If we project it onto the 2D space of $$$D$$$ and $$$C$$$, it will still be convex. By varying $$$F$$$, we can get a piecewise linear function describing all Pareto optimal solutions. From this function, we can find the minimum $$$C$$$ required to get some fixed $$$D$$$ or maximum $$$D$$$ achieve by some fixed $$$C$$$.
Since a feasible solution to a min-cost flow problem is optimal iff it has no negative cost cycles, and both successive shortest path and primal-dual never create negative cycles, they maintain optimal solutions to their current min-cost flow problems, which only differs in $$$F$$$. Thus, they effectively trace out the function as $$$F$$$ varies from $$$0$$$ to maximum. By binary searching and lerping, we can answer queries in $$$O(\log{N})$$$.
(Since the cost is integral and bounded by $$$N$$$, there are at most $$$N$$$ linear pieces.)
Time Complexity: $$$O(n^2m+q\log{n})$$$