Problem $1($Pizza Delivery, $30$ points$)$

Alice, who lives at a vertex $s$ of a directed, weighted graph $G=(V,E)($with non$-$negative

weights$),$ is going to her friend's house at vertex $h$ for dinner. Naturally, Alice wants to get

from $s$ to $h$ as soon as possible, but it appears that her friend is terrible at cooking, so along

the way she wants to get a pizza from a pizza store just in case her friend cooks something

inedible. Let's say the pizza stores form a subset of the vertices BsubV. Thus, starting at

$s,$ Alice must go to some vertex binB of her choice, and then head from $b$ to $h$ using the

shortest overall route possible $($assuming she wastes no time at the pizza store$).$ We can help

Alice reach $h$ as soon as possible, by solving the following sub$-$problems.

Compute the shortest distance from $s$ to all pizza stores binB.

Compute the shortest distance from every pizza store binB to $h.$ Note that this is the

dual of the single$-$source shortest path where we are now asking for the shortest path

from every node to a particular destination.

Combine part $1$ and $2$ to solve the full problem.

A straightforward solution is to run Dijkstra's algorithm twice $($once in part $1$ and once in

part $2).$ In this problem, you will improve this solution by running Dijkstra's algorithm only

once. Specifically, you should define a new graph $G^{\text{'}}$ on $2|V|$ vertices and at most $2|E|+|V|$

edges $($and appropriate weights for these edges$),$ so that the original problem can be solved

using a single Dijkstra call on $G^{\text{'}}.$ Briefly argue correctness of your proposed solution. $($Hint:

This is another problem on reductions. You might want to refresh your memories on Problem

$1$ in Homework $8,$ which is also a reduction problem.$)$