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),$dots,h$\_($n$)$ that want to buy the MSTs$,$ and there are m SSSP locations s$\_(1),$s$\_(2),$dots,s$\_($m$)$ in New

York. For in and jm$,$it takes t$\_($i$,$j$)$ minutes for the people from h$\_($i$)$ to reach s$\_($j$)$ if they start at $6$ am on

the day after Thanksgiving. Once they reach their intended s$\_($j$)$ 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 t$\_($i$,$j$)$ values from all n households ahead of time. They have

hired you to design an algorithm that given all t$\_($i$,$j$)$h$\_($i$)($s$\_($j$))$ 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$)$logn$)$ time

to deserve any credit.

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

Please use "the Edmonds$-$karp algorithm" to $$solve this question: