[Need help] Shortest path, but edge has 2 cost Ai and Bi, and cost of path is prod of sum Ai and Bi

Правка en6, от 3509, 2022-10-10 09:07:32
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.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en6 Английский 3509 2022-10-10 09:07:32 37 Tiny change: ' 2000$\n\n##### ' -> ' 2000$\n\nThere is no additional guarantees\n\n##### '
en5 Английский 3509 2022-10-10 09:01:12 0 (published)
en4 Английский 3509 2022-10-10 08:57:58 628
en3 Английский 3509 2022-10-10 08:48:11 560 Tiny change: 'edges $E: {e_1, e_2,... e_k}$, cost o' -> 'edges $E: \{e_1, e_2,... e_k\}$, cost o'
en2 Английский 3509 2022-10-10 08:28:54 6
en1 Английский 3509 2022-10-10 08:28:17 617 Initial revision (saved to drafts)