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

Правка en2, от 3509, 2022-10-10 08:28:54

Source: My school hosted a local ICPC format contest yesterday, this problem appeared in it. Since it is local, I cannot provide link to submit (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 a direct path from $$$u_i$$$ to $$$v_i$$$ with cost $$$A_i$$$ and $$$B_i$$$. Define cost of a path $$$U$$$ to $$$V$$$: $$$cost{U, x_1, x_2,..., x_z, V}$$$ to be product of (sum of all $$$A_x$$$) and (sum of all $$$B_x$$$) with $$$x∈{nodes in path}$$$

История

 
 
 
 
Правки
 
 
  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)