Problem S. 51. (February 2010)
S. 51. Ultra-thin clients were introduced at a certain company when its computer network infrastructure was updated. This means that desktop computers were replaced by simple devices only capable of forwarding keyboard and mouse input to a central server, and displaying the server's output on the local screen. All computations and programs are effectively run on the central server.
However, one disadvantage of this system is its sensitivity to network delays, so the server must be placed optimally such that the maximal delay from a client to the server is minimal.
Your program should determine the network delay between the server and the farthest client if the server is optimally positioned. The network topology is a tree, that is, every two nodes are connected by exactly one path. Clients are located at final nodes of the network, that is, they are the leaves of the tree. The server should be put at some inner node.
Description of the network is read by your program from the standard input. The first line of the input contains a single integer, the number of nodes . Then each of the following N-1 lines contains 3 integers separated by space: the Xi and Yi endpoints of the ith network connection (1Xi,YiN) together with its delay 0Di1000. (The time needed to process data at the two endpoints can be neglected.)
Your solution is written on the standard output. It should contain only a single line with an integer: the maximal delay in an optimal location of the server.
In the example, ,,Példa bemenet'' is sample input, ,,Példa kimenet'' is sample output, ,,Hálózati topológia'' is network topology, while ,,A szerver a bekeretezett (8-as számú) csomópontba kerül'' means that the server should be positioned at node 8 (framed).
Sample test cases: s51test.zip
Deadline expired on 10 March 2010.
|13 students sent a solution.|
|9 points:||Éles András.|
|8 points:||4 students.|
|7 points:||2 students.|
|6 points:||3 students.|
|5 points:||2 students.|
|4 points:||1 student.|