Source
My school hosted a local ICPC format contest yesterday, this problem appeared in it. Since it was for local only, I cannot provide link for submission (sorry!)
Statement
Given a weighted undirected graph $$$G$$$ with $$$n$$$ vertices and $$$m$$$ edges. Edge $$$e_i$$$ is a tuple $$$(u_i, v_i, A_i, B_i)$$$ denotes there is an edge connects $$$u_i$$$ with $$$v_i$$$, with cost $$$A_i$$$ and $$$B_i$$$. Consider path $$$u \rightarrow v$$$ is a sequence of edges $$$E: \{e_1, e_2,... e_k\}$$$, cost of $$$E$$$ is defined as product of (sum of all $$$A_x$$$) and (sum of all $$$B_x$$$) with $$$x$$$ is an edge in $$$E$$$. Calculate shortest path from node $$$1$$$ to all other nodes.
Contraints
- $$$1 \leq n, m \leq 2000$$$
- $$$1 \leq A_i, B_i \leq 2000$$$
There is no additional guarantees
Sample Tests
Input 1
4 4 1 2 2 4 3 4 4 1 4 2 1 1 1 3 3 1
Output 1
8 3 14
Output shortest path from $$$1$$$ to $$$i (2 \leq i \leq n)$$$:
- Shortest path from node $$$1 \rightarrow$$$ node $$$2$$$ is the edge $$$(1,2)$$$, with cost $$$2 \times 4 = 8$$$
- Shortest path from node $$$1 \rightarrow$$$ node $$$3$$$ is the edge $$$(1,3)$$$, with cost $$$3 \times 1 = 3$$$
- Shortest path from node $$$1 \rightarrow$$$ node $$$4$$$ are $$$(1,3),(3,4)$$$ with cost $$$(3+4) \times (1+1) = 14$$$. The other path is $$$(1,2),(2,4)$$$ has cost $$$(2+1) \times (4+1) = 15$$$ is not the shortest path.
Input 2
3 2 1 2 2 5 2 1 3 3
Output 2
9 -1
$$$-1$$$ means there is no path from $$$1$$$ to that node.
Auto comment: topic has been updated by 3509 (previous revision, new revision, compare).
You could use a Bellman-Ford like solution, except that instead of the best cost, you maintain a set of the candidate pairs $$$(\sum_{e} a_e, \sum_{e} b_e)$$$ for your shortest path. Note that it is safe to discard $$$(x, y)$$$ from the set of candidates if there is another pair $$$(x', y')$$$ with $$$x' \le x$$$ and $$$y' \le y$$$. So the candidate set will be sorted in decreasing order by $$$x$$$ when it is sorted in increasing order by $$$y$$$. Merging two sets (with this property) of size $$$s_1, s_2$$$ can be done in $$$O((s_1 + s_2) \log \min(s_1, s_2))$$$.
Note that this algorithm will terminate in at most $$$n - 1$$$ relaxations, since for any path, we can reduce it to a simple path while reducing its cost. A naive bounding argument leads to a complexity of $$$O(nm^2 A \log (Am))$$$ where $$$A = \max_i \max(A_i, B_i)$$$, but I haven't been able to construct an example that shows that this bound is asymptotically optimal.
On discussion with jeroenodb and ToxicPie9, it turns out that you can solve this in $$$O(m(nA)^{2/3}\log(Anm))$$$ time. Firstly, note that we don't really need Bellman-Ford, and you can do Dijkstra while maintaining these candidate sets, which brings down complexity to $$$O(nmA \log(Anm))$$$. Using ideas similar to that in BOI '11 P6, we can note that we only need the convex hull of $$$(S_A, S_B)$$$ (where $$$S_A$$$ is the sum of $$$A_i$$$-s on the path, etc.). To show that all the reachable relevant $$$(S_A, S_B)$$$ pairs are generated while relaxing during Dijkstra, note that whenever we move along a path, we get $$$S_A, S_B$$$ incremented by constants, which corresponds to a translation of the plane. In the end, by the linked problem, we get that the optimal point is on the convex hull of the sums of $$$A$$$ and $$$B$$$, so the initial point can't be strictly inside the convex hull of its possible sums. Another observation is that by a recent problem in Meta Hacker Cup, if the coordinates are restricted to lattice points in a box of size $$$N \times N$$$, there can be at most $$$O(N^{2/3})$$$ points in the convex hull. Applying this to $$$N = nA$$$, we get the claimed complexity (the $$$\log$$$ comes from Dijkstra and incremental convex hull, and you can reduce it to $$$\log \log$$$ by using van Emde Boas trees).
This problem seems to have been taken from COCI17 Ceste. There is no public editorial as far as I know, but the submissions are public on oj.uz.