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
rishi_devan:
2016-08-21 19:48:16
Straight-forward Dijkstra's algorithm |
|
pd42slok:
2016-08-20 21:09:26
can be solved by kruskal, so mst tag |
|
nsitsk:
2016-07-08 20:18:11
@admin, Please correct the tag. This question is on dijkstra. Not MST. |
|
iharsh234:
2016-07-08 12:47:39
stl rocks!! |
|
distort:
2016-06-10 05:33:11
Only accepted in python 3.4!!
|
|
vijay kumar paliwal:
2016-06-03 14:11:50
Learnt Dijkstra with priority queue.. first problem solved using priority queue!
|
|
Ray Brish Bhanu:
2016-04-15 11:22:29
for edges take structure not pair..caused me several tle
|
|
vedang:
2015-12-05 21:03:34
Not MST, but Dijkstra! |
|
kartikay singh:
2015-10-19 15:27:59
Djikstra + priority_queues
|
|
sarvagya:
2015-09-26 00:11:35
Djikstra with sets -> 0.05s
|
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 |