Sherlock In Thuvax
All submissions for this problem are available.
Sherlock works as a spy in the country of Thuvaks. Thuvaks has N cities. All roads in Thuvaks are bidirectional and have a positive length. To add to the already existing overwhelming misery of Thuvaksian citizens, the recent floods have destroyed several roads in the country such that there is only one simple path between every pair of cities.
Sherlock has an assignment. Everyday he starts from a city in the morning and has to travel to all other cities by evening. He must do this repeatedly for K days. The starting city for the first day is A. The path taken by Sherlock on a particular day is given by a sequence of roads, where each adjacent roads in the sequence is connected to a common city. The total distance of such a path is given by the sum of all the lengths of the roads in the path. The path has to start at a particular city and should cover all the cities. Due to Sherlock's stunning character, people remember him very well. In order to save his cover, he does not want to start the day from the same city more than once. During the night time he travels to the city from where he wants to start the next day of his mission.
Given the description of road network of Thuvaks, length of his mission K (in days) and his starting city A(1<=A<=N) minimize the sum of the distance he needs to travel during day time over the period of K days of his mission.
First line contains three space separated integers N, K and A. Next N-1 lines consists of three space separated integers X, Y and C, implying that the city X is connected to city Y with a bidirectional road of length C.
Print a single line containing the answer ie. the sum of distance he needs to travel during the day time over the period of K days to complete his mission.
- 1 ≤ N ≤ 10^5
- 1 ≤ K, A, X, Y ≤ N
- 1 ≤ C ≤ 10^5
3 3 1
1 2 10
1 3 20
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, 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, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.