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
sarthak_19:
2020-07-09 13:43:03
Dijkstra with set works fine |
|
nathanaxel:
2020-04-01 04:25:07
why do ikeep getting TLE ::"( |
|
purplecs:
2019-11-13 17:13:35
|
|
jnu_siddharth:
2019-04-02 08:19:52
Good Problem to apply Dijkstra.
|
|
ort:
2018-11-16 15:25:46
Nothing special here, just dijkstra... |
|
joqsan_77:
2018-08-04 19:48:56
MST doesn't work here. |
|
paroaro:
2018-07-19 17:31:14
ez ternaryserch |
|
karan_yadav:
2018-07-11 19:44:09
@indra Generally speaking MST is the minimum cost involved in connecting all the nodes of a graph. It doesn't guarantee that given path between two nodes is of minimum cost.
|
|
ankit1cool:
2018-06-20 20:00:56
use dijkstra's and break as soon as destination is found |
|
selva1996:
2018-06-11 21:54:01
Use Struct instead of Pair...for me using Pair was giving me time out.... Last edit: 2018-06-11 21:54:33 |
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 |