IOI '13 - Brisbane, Australia

Dreaming

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.

Examples

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.

Input Format

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 A_i, B_i (0 ≤ A_i, B_i ≤ N - 1), and T_i (0 ≤ T_i ≤ N - 1), specifying the endpoints and travel time of each pre-existing trail, so that the i^th line joins billabongs A_i to B_i, and takes T_i days to travel in either direction.

Output Format

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.

Sample Input

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

Sample Output

18

Subtasks

All Submissions
Best Solutions

Point Value: 20 (partial)
Time Limit: 1.00s
Memory Limit: 64M
Added: Jul 15, 2013

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

If often takes many minutes to complete a submission on this question, clogging up the site's judges and preventing submissions to other problems. I think PEG should either cut down on the amount of data, add a short-circuiting grader or allow users to abort wrong submissions.

The wall-clock time to judge one submission seems to be about 5 minutes. A single instance of this is acceptable; while it takes some time to judge, other submissions can actually still be judged in the meanwhile.

However, making three submissions to this problem in as many minutes will indeed put significant strain on the Judge. Perhaps the best way to go about this is to give users the option of immediately halting judging, earning 0 on the remaining cases. *shrug*