##### 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.↵
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.↵
