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
ameyanator:
2018-04-25 08:46:20
My dijkstra with multiset runs in 0.04 secs. But how to solve with MST? |
|
nilesh8757:
2017-10-20 21:38:58
Why my solution is not getting accepted. I mean , after clicking submit button ,it's not running.:( |
|
sunny:
2017-08-14 21:53:49
AC in one Go :-). Dijkstra's. |
|
marwankhaled:
2017-08-01 18:34:31
My 50th :D
|
|
indra_5672:
2017-07-03 09:34:35
I solved it using dijkstra but i think we can solve it using mst because after finding mst we can find path between given nodes if it exists then it will be minimum time path. tell me if i am wrong @rohit9934 @admin @ nsitsk |
|
rohit9934:
2017-06-14 19:54:37
AC in a go using Dijkstra.
|
|
code_aim:
2017-05-25 20:17:48
very weak test cases!! |
|
testing java:
2017-01-14 14:24:48
@pd42slok as far as I know, you can't solve shortest path problem using an MST algorithm (such as kruskal). If i'm wrong, please feel free to enligh me. Otherwise, @admin - please correct the tag.
|
|
flyingduchman_:
2016-12-29 17:35:13
Dijkstra with priority-queue of STL ac .04s |
|
lt:
2016-11-29 07:41:17
Dijkstra rocks. Done using sets! |
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 |