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 $$$X$$$ 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}$$$