The persons need to get the food and go to the party city. Since the graph is undirection, we can take it as from the food cities to reach each person and party cities. So totally two steps.1) get num_person of shortest path data using Dijkastra alg. Sources are food cities. I run num_person times of Dijkastra with no destination.2) get shortest time for people to get foods. It's classical assignmen problem. Hungrian alg is the choice. For python, I use scipy.optimize.linear_sum_assignment which is pretty good.
The final step is enumerate each city and calculate time to go to food cities. The city with least time is the one.
I could use the alg to reach around 40 queries, then step 1 takes too much time because of too many persons and roads. Then I use ThreadPool, it could 50s even futhur but still far from 141 queries. Step 1 needs further optimization.