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
sujit yadav:
2015-09-18 23:26:30
mst is not dijsktra ... wrong tag :p |
|
moovon:
2015-08-23 07:30:30
dijsktra is fine enough |
|
shuks:
2015-07-30 18:08:34
STL <3 |
|
Tim Wargon:
2015-05-15 21:43:18
NO...Dijkstra without prior. queue works fine too. Last edit: 2015-05-16 09:47:31 |
|
sai krishna:
2015-03-08 06:04:11
ha ha ha AC :) |
|
Hahaha:
2014-12-03 18:52:41
Simple dijsktra with prioirty queue will pass very easily |
|
Varun Gambhir:
2014-08-30 13:21:02
Simple dijikstra will work fine |
|
Ayur Jain:
2014-06-27 13:31:33
Dijsktra via priority queue is fast enough |
|
Itachi:
2014-06-25 13:22:51
int is enough. ll gave a TLE. |
|
Sujith Konanki:
2014-03-22 20:32:13
<snip> working in ideonw but giving SGVABRT help
|
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 |