| Submit | All submissions | Best solutions | Back to list |
SNYC3 - On the Way to Find Chris |
Do you know the famous game THE KING OF FIGHTERS? If the answer is yes, I'm sure you know THE THREE BLACK GROUP: Chris, Shermie and Yashiro. Today Chris is invited to one of his friends' home to play THE KING OF FIGHTERS.Blue Mary is now at Chris' home, she knows where Shermie's and Yashiro's home is, but she doesn't know where Chris actually is.So she decides that:
- If Yashiro's home is nearer than Shermie's, she will go to Yashiro's home first, if she doesn't find Chris, she will then go to Shermie's, and vice versa.
- The map of the city is strange. Each of the houses is assigned to a unique number in the range[1,n], where n is the number of houses. Between some pairs of houses there are some roads. There exists one and only one path from any house to any other house. She will go along the only path between the two houses.
Unfortunately, you don't know where Chris' home actually is, and the same as Yashiro's and Shermie's. Now you are interesting in the maximum time from the time when Blue Mary starts from Chris' home to the time when Blue Mary finds Chris in the worst case.
Input
The number of test cases T is given in the very first line.T blocks follow.
For each test case, the first line contains 2 space-separated integers N(3<=N<=200000) and M, which denotes the number of houses and the number of roads in the city.M lines follow, each contains 3 space-separated integers x,y,z(1<=x,y<=n,1<=z<=109).It tells us there exist a road between house No.x and house No.y, and to go from x to y or from y to x along this road will take z minutes.No two roads are repeated.
Output
For each test case you should output a single line, which contains a single integer - the maximum time measured in minutes.
Example
Input: 1 4 3 1 2 1 2 3 1 3 4 1 Output 4Warning: large Input/Output data, be careful with certain languages
Scoring
The shortest code (the less number of bytes) the better. The number of points displayed in the ranking is scaled so that it is equal to 10 for the contestant whose solution is the shortest, and proportionally less for all solutions with longer codes.
| Added by: | kuszi |
| Date: | 2009-12-31 |
| Time limit: | 1s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | ADA95 ASM32 ASM64 BASH BF C CSHARP C++ 4.3.2 CPP CPP14 C99 CLPS LISP sbcl LISP clisp D ERL FORTRAN HASK ICON ICK JAVA JS-RHINO LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON RUBY SCALA SCM guile SCM qobi ST TCL TEXT WHITESPACE |
| Resource: | Chinese National Olympiad in Informatics 2003,Day 2; translated by Blue Mary |
RSS