All submissions for this problem are available.
Due to the large number of events being held at Cognizance this year, all major media houses have sent teams of reporters to cover the event. The reporters don't feel like walking too much, so they gather at the central registration area and decide that only a limited subset of them would go out to the site of the events and bring back information. Being new to the campus, each reporter that goes out to gather information will come back to the registration area using the same route he used to reach an event area. Being smart, the reporters decide upon the following policies:
- All information-gathering reporters leave the registration area simultaneously.
- Reporters will be sent out in a way which ensures that no two reporters cross paths during the course of their coverage of events. This means that reporters may not walk side by side or in opposite directions on the same road between two events, thus preventing wastage of effort.
- Each reporter will cover an event taking place in the vicinity of his location if and only if there is no other reporter who can cover that event using less effort.
- Once a reporter returns to the registration area, he will not leave it again.
Having no knowledge of the campus, they turn to you for help. To help them, you need to provide the following information:
- The minimum number of reporters that need to be sent out so that the effort expended in total by all reporters is minimized, yet all events are visited.
- The amount of the effort expended by the reporters as a whole while covering the events. Assume that reporters who do not leave the central registration area expend zero effort.
You are supplied with the following details:
- The roads that link various event locations.
- A sequential labeling of the event locations (with location 1 corresponding to the central registration area)
- The effort expended in moving from an event location i to its nearby event locations.
Note: The registration area is also an event location. Assume that the number of reporters in the group is sufficient to ensure that each event can be covered individually.
Line 1: N - The number of event locations. 1 <= N <= 100. Event Locations are labeled 1, 2, 3... etc. In sequence.
Line 2: L K
Where L = the event location sequence number
and K = the number of roads connecting to this event location 1<=15<=K
Line 3 to K+3: D E
Where D = the nearby event location sequence number
and E = the effort expended in moving along this road. 1 <= E <= 1000
Lines 2 and 3 to K+3 are repeated N times - once for each event location
Line 1: M
Line 2: X
Where M = minimum number of reporters to be sent out so as to minimize the total effort
and X = the minimum effort that will be expended
5 1 2 2 344 5 707 2 3 1 344 3 482 5 652 3 1 2 482 4 1 5 281 5 3 1 707 2 652 4 281
|Time Limit:||5 - 12 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.4, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.