IOI '13 - Brisbane, Australia
This story takes place a long time ago, when the world was new and the IOI had not yet been dreamt.
Serpent lives in a land which has N billabongs (water holes), numbered 0, …, N - 1. There are M bidirectional trails, joining pairs of billabongs, which Serpent can travel along. Each pair of billabongs is connected (directly or indirectly) by at most one sequence of trails, though some pairs of billabongs may not be connected at all (thus, M ≤ N - 1). Each trail takes a certain number of days for Serpent to travel along it: this number may be different for each trail.
Serpent's friend, Kangaroo, wishes to make N - M - 1 new trails, so that it is possible for Serpent to travel between any pair of billabongs. Kangaroo can create trails between any pair of billabongs, and every trail that Kangaroo creates will take L days for Serpent to travel along it.
Additionally, Kangaroo wants to make Serpent's travels as fast as possible. Kangaroo will build the new trails so that the longest travel time between any two billabongs is as small as possible. Help Kangaroo and Serpent determine the longest travel time between any two billabongs, after Kangaroo has built the new trails in this way.
In first the picture below there are N = 12 billabongs and M = 8 trails. Suppose that L = 2, so that any new trail will require Serpent 2 days to travel. Then Kangaroo could build three new trails:
- between billabongs 1 and 2;
- between billabongs 1 and 6;
- between billabongs 4 and 10.
The second picture below shows the final set of trails. The longest travel time is 18 days, between billabongs 0 and 11. This is the smallest result possible - no matter how Kangaroo builds the trails, there will be some pair of billabongs that requires Serpent to travel for 18 days or more.
The first line of the input will consist of 3 integers: N (1 ≤ N ≤ 100 000), the number of billabongs, M (0 ≤ M ≤ N - 1), the number of trails that already exist, and L (1 ≤ L ≤ 10 000), the time in days that it takes Serpent to travel along a new trail.
The remaining M lines of the input will each contain 3 integers Ai, Bi (0 ≤ Ai, Bi ≤ N - 1), and Ti (0 ≤ Ti ≤ N - 1), specifying the endpoints and travel time of each pre-existing trail, so that the ith line joins billabongs Ai to Bi, and takes Ti days to travel in either direction.
One integer - the greatest travel time (measured in days) between any pair of billabongs, assuming that Kangaroo has added N - M - 1 trails in such a way that all billabongs are connected and this greatest travel time is as small as possible.
12 8 2 0 8 4 8 2 2 2 7 4 5 11 3 5 1 7 1 3 1 1 9 5 10 6 3
|Subtask||Percent of Points||Additional Input Constraints|
|1||14||M = N - 2, and there are precisely one or two preexisting trails leading from each billabong.|
In other words, there are two sets of connected billabongs, and in each set the trails form an unbranching path.
|2||10||M = N - 2 and N ≤ 100|
|3||23||M = N - 2|
|4||18||There is at most one pre-existing trail leading from each billabong.|
|5||12||N ≤ 3,000|
Point Value: 20 (partial)
Time Limit: 1.00s
Memory Limit: 64M
Added: Jul 15, 2013
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3