$3$ Not So Crazy Delivery

PNPenguins are running a new food delivery business where they wish to deliver ice$-$cakes to all their

fellow penguins in the shortest amount of time. The penguins community is a network consisting

of $m$ households total and $r$ two$-$way$/$bidirectional roads. The time it takes to travel between two

households $h_1,h_2$ is given by $c(h_1,h_2).$ Due to limited budget, PNPenguins can only afford to have

a maximum of $k$ delivery centers within the community. PNPenguins have found a subset of $n$

households $(m>>n>k)$ within the community who are willing to sell their home to PNPenguins

and become a delivery center. For this problem, assume that households always get ice$-$cakes delivered

by the closest delivery center to them.

a$)$ Design an algorithm that helps PNPenguins to find the most optimal locations of delivery centers;

that is$,$ a set of delivery centers that minimizes the maximum delivery time needed to all households.

This algorithm need not run in polynomial time with respects to all variables. Please provide a

$3-$part solution.

Hint: First write an algorithm which computes the maximum delivery time for some fixed set of

delivery centers. Then, use this algorithm to check the maximum delivery time for each possible set

of delivery centers.

PNPenguins have now decided to use the locations you chose from part a$).$ But right before they start

the delivery service, Pesla $($a highly innovative iceship company headquartered in PNP$-$Borderland$)$

releases a new magical iceship model that allows passengers to skip over the $t$ most time$-$consuming

roads along any of their journeys. PNPenguins all agree to integrate this new technology into their

delivery business.

b$)$ Design an algorithm that finds the updated$/$new maximum delivery time for each household.

Please provide a $3-$part solution.

Hint: create a graph such that edges and nodes encode information about whether an edge is skipped

when traversed by a graph algorithm.