ZOJ Problem Set - 3584
The United Federation of Planets has just improved their long range transporter technology which can be used for inter-planetary transportation. Being the largest manufacturer and distributor of genuine food (operated by Ferengis of course) you wish to take advantage of this opportunity the build a distribution network to lower your operation cost.
So among all the planets you do business with you wish to choose a subset of them as production base and distribute to the rest of the planets. The cost of distribution is only proportional to the distance between two planets, and not related to the amount of food being transported. That being said, you can transport from production planet A to planet B and then from planet B to planet C to cover both B and C.
To set up the network you only need to know which planets to select as production base. You somehow hosted a contest to ask the citizens of those planets to figure out the selection, partially because that's a great advertisement in itself. The problem is that you received tons of submissions and need a way to determine which of them deserve the prizes, and the task soon becomes a nightmare... Could you help to finish the task?
Input has multiple test cases.
First line of each test case has three integers N which is the number of planets, M which is the number of production planets to select, and K which is the number of submissions (2 ≤ N ≤ 500, 2 ≤ M ≤ 10, M ≤ N, 1 ≤ K ≤ 1,000,000).
Next N lines each has three integers which is the three dimensional coordinate of each planet in light year (absolute value ≤ 10,000).
Next K lines each has M integers which is one submission with each number referring to a planet given above. The index is 1 through N.
Write a "Yes" or "No" for each submission meaning if the selection of production base is optimal that leads to lowest cost of transportation.
5 3 3 0 0 0 1 1 1 2 2 2 4 4 4 5 5 5 1 2 3 1 3 4 1 4 5
No Yes Yes
Author: WU, Jiazhi
Contest: ZOJ 10th Anniversary Contest