Remember the problem, "Trip Compulsion" in Amritapuri site? I hope you've solved it and feel that it is too easy for you, cuz here comes the ultimate, testdata-enhanced version of the problem!!
You're faced with the same problem but now the number of roads is now way larger (now up to 30000!). Can you still tackle it?
p.s. For the original problem description, please see Trip Compulsion Original
The first line contains T, the number of test cases. The first line of each test case contains two space separated numbers - N (the number of junctions) and R (the number of roads). The second line of each test case contains the two space separated numbers - start (the starting junction of your trip) and end (the ending junction of your trip). Each of the next R lines contains three space separated numbers - from (the starting junction of a road), to (the ending junction of a road) and length (the length of the two-way road connecting from and to).
There MAY OR MAY NOT be multiple edges between same pair of nodes.
For each test case, output a single line containing one integer - the lowest possible difference. If no trip is possible between start and end, output a single line saying "NO PATH" (quotes for clarity).
0 <= start, end, from, to < N
1 <= length <= 2,000,000,000
start and end will be different.
3 3 2 0 2 0 1 1000 1 2 5000 2 1 0 1 0 1 1000 2 0 0 1
4000 0 NO PATH
Migrated from old NTUJ.
orginal: icpc amritapuri site 2010, revised: kelvin
| No. | Testdata Range | Score |
|---|