The figure below describes the network of streets in a city where Motabhai sells $\text{pakoras}$ from his cart. The number next to an edge is the time (in minutes) taken to traverse the corresponding street.
At present, the cart is required to start at point $s$ and, after visiting each street at least once, reach point $t$. For example, Motabhai can visit the streets in the following order $$s-a-c-s-e-c-d-a-b-d-f-e-d-b-t-f-d-t$$
in order to go from $s$ to $t$. Note that the streets $\{b,d\}$ and $\{d, f \}$ are both visited twice in this strategy. The total time taken for this trip is $440$ minutes [which is, $380$ (the sum of traversal times of all streets in the network) $+ 60$ (the sum of the traversal times of streets $\{b,d\}$ and $\{d,f\}$)].
Motabhai now wants the cart to return to $s$ at the end of the trip. So the previous strategy is not valid, and he must find a new strategy. How many minutes will Motabhai now take if he uses an optimal strategy?
Hint: $s, t, b$ and $f$ are the only odd degree nodes in the figure above.
- $430$
- $440$
- $460$
- $470$
- $480$