HIGHWAYS - Highways
A number of cities are connected by a network of highways. Each highway is bidirectional and connects two cities, with a given travel time. What is the shortest time to get from a given city to another given city?
Input
The first line of input contains the number of test cases.
Each test case starts with a line containing the number of cities n (2 ≤ n ≤ 100000), the number
of highways m (1 ≤ m ≤ 100000), the starting city and the ending city. Cities are numbered from
1 to n.
Then m lines follow, each describing one highway. The description consists of the two distinct city
numbers and the time in minutes to travel along the highway. The time will be between 1 and
1000.
Output
For each test case output a single line containing the minimum time it takes to get from the start to the destination. If no connection exists, output NONE.
Example
Input: 2 4 2 1 4 1 2 5 3 4 5 4 4 1 4 1 2 5 2 3 5 3 4 5 4 2 6 Output: NONE 11
hide comments
Samer:
2014-02-25 13:40:07
dijkstra <3 <3 <3 |
|
vishnu:
2014-02-14 10:42:35
dijikstra works fine for me :) |
|
Abhishek Gupta:
2014-02-07 13:25:06
dijkstra is slow (1.29sec)...
|
|
Abhimanyu:
2013-12-19 20:58:29
int works fine :) |
|
Python:
2013-10-17 06:33:56
does the test cases end with EOF
|
|
Prakash:
2013-08-02 04:55:29
getting TLE, used O(ElogV) for dijkstra! Help |
|
srikardurgi:
2012-10-15 16:27:55
|
|
Simón Murillo Gómez:
2012-08-20 01:33:46
Nothing special here. Just take care about the constraints Last edit: 2012-08-20 01:53:28 |
|
张翼德:
2012-04-17 14:03:01
My program is working fine on ideone...but giving SGVABRT here on spoj....==><snip> Last edit: 2023-02-22 20:28:38 |
Added by: | Daniel Gómez Didier |
Date: | 2008-11-18 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |
Resource: | Circuito de Maratones ACIS / REDIS |