You are given a directed graph $G=(V,E)$ with non$-$negative edge weights $w(u,v)$ representing

the time it takes to go from a node $u$ to $v$ when $u$ and $v$ are directly connected. $($We assume all

$w(u,v)<mi></mi>$ for simplicity.$)$ Some subset $F$ of vertices in $G$ are pharmacies, while some other

subset $D$ are doctor offices. You live at a node $s$ and have a medical emergency. You now need to

go to some doctor office dinD to get a prescription for the drug, then to some pharmacy finF,

and finally back home. Recall that a proper output must be the full path described above. However

some paths are better then others. Solve the following variants of this problem, where each variant

describes how to compare different valid paths when choosing the optimal path you are looking for.

Each variant could be solved by one "clever" run of the Dijkstra's algorithm, on an appropriate

modification of our graph $G.$ You have to explain your choice and state the resulting running time

as the function of $n($remember$,$ we assume $m=(n^2)$ here, as

$($a$)(3$ points$)$ Assume only the distance from your home $s$ to the doctor's office matters $($e$.$g$.,$

you need to get doctor's emergency help asap, and the time it then takes to the pharmacy

and back home are not important$).$

$($b$)(5$ points$)$ Assume only the distance between the doctor office $d$ and the pharmacy $f$ matters.

E$.$g$.,$ the doctor would perform some painful procedure, but does not have a tranquilizer to

numb the subsequent pain. Thus, you must choose an office dinD and pharmacy finF with

the smallest distance between them, but do not care how far $d$ is from $s$ or $s$ is from $f.($E$.$g$.,$

if there is a pharmacy in some doctor's office in Antarctica, you do not mind going there, as

the answer you care will be $0,$ even if you live in NYC$.)$

$($Hint: Add an artificial source node $s^{\text{'}}$ to $G$ and compute the distance from $s^{\text{'}}$ to "fill the

blank" in your new graph.$)$

$($c$)(5$ points$)$ Assume only the distance from the pharmacy $f$ back to home $s$ matters. E$.$g$.,$

the medicine must be administered by the pharmacist and has some quick side effect, so you

must get to bed asap after taking the medicine in the pharmacy.

$($Hint: Two solutions are possible: one does something to the edges of $G,$ and the other again

adds some artificial source similar to part $($b$).)$

$($d$)(7$ points$)$ Finally, assume that the overall trip time from $s$ to $d$ to $f$ to $s$ matters. Show how

to combine the ideas in parts $($a$)-($c$)$ to solve this variant.

$($Hint: Make several "copies" of $G$ and connect them "appropriately" by $0-$weight edges.

The copies will ensure that every valid path must pass through a doctor office followed by a

pharmacy.$)$