Task $4.[70$ Points $]$ SSSP sells MSTs at a TSP during BFS

SSSP$5$ is a place where people go to buy apple$6.$ During the BFS$7$ this year, they will sell an MST$8$ at a TSP$9.$ SSSP has set such an APSP$10$ for the MSTs that no one can refuse to buy them.

SSSP has many locations in New York, and all locations will offer the deal. Suppose that there are n households h$1,$ h$2,...,$ hn that want to buy the MSTs$,$ and there are m SSSP locations s$1,$ s$2,...,$ sm in New York. For $1$ i $$ n and $1$ j $$ m $,$it takes ti$,$j minutes for the people from hi to reach sj if they start at $6$am on the day after Thanksgiving. Once they reach their intended sj they will join the queue waiting outside the store. No one will be allowed to join the queue after the store opens. One household will be served every minute immediately after the opening of the store. So$,$ if people from k households end up waiting in the queue, it will take exactly k minutes for all of them to get their MSTs$.$

The CS$11$ department at SSSP has collected all ti$,$j values from all n households ahead of time. They have hired you to design an algorithm that given all ti$,$j values can determine which household $($hi$)$ should go to which store location $($sj$)$ and at what time the stores must open so that the last household to be served can be served as early as possible $($measuring time from $6$am on the day after Thanksgiving$).$ They require that all store must open at exactly the same time and every household must be served at some $($and exactly one$)$ location. The stores will remain open until all n households are served.

Explain your algorithm and analyze its running time. Your algorithm must run in O $($m$3$n$3($m $+$ n$)$ log n$)$ time to deserve any credit.$$ not more that that$$

Hint: You may need to use network flow to solve this problem.

$----------------------------------------------------------------------------------------------------------------------------------$

$5$SSSP $=$ Super Store for Superior Products

$6$apple $=$ astonishingly precious products at low expense$$

$7$BFS $=$ Black Friday Sales

$8$MST $=$ Mind$-$bloggingly Superior Thing

$9$TSP $=$ Tantalizingly Slahsed Price

$10$APSP $=$ Amazingly Puny Sale Price$$

$11$CS $=$ Customer Service