A university with a new campus and thirteen buildings wants to open some coffee shops such that students are not more than 5 minutes away from one regardless which building they are at. The university marked which buildings are 5 minutes or less from each other (Figure 1). Each node is a building, and each arc represents that the buildings are 5 minutes apart or less (connected). 3 6 7 2 4 5 6 10 11 8 12 13 Figure 1: Campus Network (a) What is the minimum number of coffee shops that the university has to open? (b) Each coffee shop to service exactly two building. Note: this is an extension to part (a), we still want to minimize the number of coffee shops to be open. (c) The campus wants to open coffee shops, restaurants, or dining halls in the buildings. The coffee shops serve only coffee. The restaurants serve only food. The dining halls serve coffee and food. The university wants a food service to be reachable within 10 minutes or less from each building (two links on the network provided). For example, If a food provider (either restaurant or dining hall) is opened in building 6, then it is reachable to students in buildings 1, 4, 8, and 11 as well, but not from buildings 5 or 12. They still would like to maintain the coffee providing to be at 5 minutes or less. The cost of opening a coffee shop is $10K, a restaurant is $15K, and a dining hall is $27K. What is the least cost for this project such that each building is covered by coffee and food?