[Need help] Shortest path, but edge has 2 cost Ai and Bi, and cost of path is prod of sum Ai and Bi
Difference between en4 and en5, changed 0 character(s)
##### 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$↵

##### Sample Tests↵
###### Input 1↵
<pre class="prettyprint">4 4↵
1 2 2 4↵
3 4 4 1↵
4 2 1 1↵
1 3 3 1↵
</pre>↵

###### Output 1↵
<pre class="prettyprint">8↵
3↵
14↵
</pre>↵

Output shortest path from $1$ to $i (2 \leq i \leq n)$:↵
<ul>↵
<li> Shortest path from node $1 \rightarrow$ node $2$ is the edge $(1,2)$, with cost $2 \times 4 = 8$</li>↵
<li> Shortest path from node $1 \rightarrow$ node $3$ is the edge $(1,3)$, with cost $3 \times 1 = 3$</li>↵
<li> 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.</li>↵
</ul>↵


###### Input 2↵
<pre class="prettyprint">3 2↵
1 2 2 5↵
2 1 3 3↵
</pre>↵

###### Output 2↵
<pre class="prettyprint">9↵
-1↵
</pre>↵

$-1$ means there is no path from $1$ to that node.↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en6 English 3509 2022-10-10 09:07:32 37 Tiny change: ' 2000$\n\n##### ' -> ' 2000$\n\nThere is no additional guarantees\n\n##### '
en5 English 3509 2022-10-10 09:01:12 0 (published)
en4 English 3509 2022-10-10 08:57:58 628
en3 English 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 English 3509 2022-10-10 08:28:54 6
en1 English 3509 2022-10-10 08:28:17 617 Initial revision (saved to drafts)