Money in Thuvax
All submissions for this problem are available.
The kingdom of Thuvax is divided into N regions. Every pair of regions is connected by atmost 1 road (weighted and bidirectional). Among the N regions, the 0th(zeroth) region is the headquarters, represented by X. The headquarters requires money for the daily functioning of Thuvax. For this, a messenger has to travel to every city in Thuvax informing the people about the requirement of money in the headquarters, while travelling as less distance as possible. It is a known that the messenger can reach all the regions. He has to choose one of the paths that matches with the below rules:
1. He starts his journey from the Headquarters, and ends at the Headquarters.
2. From a region Y, he can either take the path to an unvisited city next, or go back one region in the path from the Headquarters to region Y (which is obviously visited).
3. When he is at the headquarters, he always moves to a new region that is unvisited, while it is possible to do so.
It is also known that all the roads in Thuvax are of different length (or weight).
Now from every region, the representatives go to the Headquarters with their money, while making sure that they use only those paths used by the messenger. This way, people from all regions deposit their money at the headquarters.However, the minister of Thuvax has a plan. He has K trusted members in this council and he plans to place them at different regions. Each will collect the money from the representatives of all regions that pass through that member's region, so that they need not travel all the way to the headquarters. Obviously, representatives from the same region as that of the minister need not travel at all. Assign the members to the regions so that the total distance to be travelled by the representatives is minimised.
The first line of the input contains 3 integeres : N (the number of regions, including the headquarters), E (the number of roads) and K(the number of members in the council).
The next N-1 lines contain the number of representatives in the regions from 1 to N-1. The headquarters has no representatives.
The next E lines describe the roads connecting the regions : The first 2 integers in each line denote the regions connected by the road. The 3rd integer denoted the weight/length of the road.
Print an integer - the minimum sum of distances that the all the representatives have to travel.
3 <= N <= 100
1 <= K <= 50
0 <= number of representatives in a region <= 10000
0 <= distance/weight of a road <= 10000
4 5 2
0 1 1
0 2 10
0 3 5
1 2 200
2 3 500
Explanation : In this case, the messenger can choose this path : 0->1->0->2->0->3->0, since this way he has to travel minimum distance. Now, the representative from region 1 have to follow the meesenger's path towards the headquarter, so they go from 0->1. Similarly from regions 2 and 3. We can place 2 members of the council. They can be placed in regions 2 and 3 to minimize the cost of travelling. This way, only 10 representatives from region1 have to travel a distance of 10 units (each has to travel 1 unit), which is the minimum we can obtain.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.