EZDIJKST - Easy Dijkstra Problem

no tags 

Determine the shortest path between the specified vertices in the graph given in the input data.
Hint: You can use Dijkstra's algorithm.
Hint 2: if you're a lazy C++ programmer, you can use set and cin/cout (with sync_with_stdio(0)) - it should suffice.

Input

first line - one integer - number of test cases
For each test case the numbers V, K (number of vertices, number of edges) are given.
Then K lines follow, each containing the following numbers separated by a single space:
ai, bi, ci
It means that the graph being described contains an edge from ai to bi, with a weight of ci.
Below the graph description a line containing a pair of integers A, B is present.
The goal is to find the shortest path from vertex A to vertex B.
All numbers in the input data are integers in the range 0..10000.

Output

For each test case your program should output (in a separate line) a single number C - the length of the shortest path from vertex A to vertex B. In case there is no such path, your program should output a single word "NO" (without quotes)

Example

Input:
3
3 2
1 2 5
2 3 7
1 3
3 3
1 2 4
1 3 7
2 3 1
1 3
3 1
1 2 4
1 3

Output:
12
5
NO

hide comments
mewtomat7: 2017-05-22 03:24:30

Don't assume that the graph is undirected.

Last edit: 2017-05-22 03:24:46
onkar14_n: 2017-05-07 14:40:39

AC in one go 0.19 s.
If you code in JAVA don't use Scanner instead use FASTER I/O.

Here is a link for faster i/o in JAVA
http://www.geeksforgeeks.org/fast-io-in-java-in-competitive-programming/

Happy Coding :-)

gulsntils_12: 2017-04-27 19:38:51

AC in one go with 0.12 sec in java.
I recommend using fast I/O.

abhishek18620: 2017-02-15 23:16:25

nodes r definitely more than 1000..so dont hardcode it for 1000.

aliosm: 2016-12-23 19:03:16

AC first GO!

tregiengchan: 2016-12-16 10:57:40

Accept with C++ (g++ 14), but not C++ (g++ 3.4.2)

square1001: 2016-08-06 11:58:58

I got AC after 2 internal errors...

shubh809: 2016-08-05 16:21:19

Last edit: 2016-11-10 12:27:28
akhileshsoni96: 2016-07-18 22:29:22

please submit in C++(g++ 14) got A.C :)
Be careful for Directed graph :P

Last edit: 2016-07-18 22:30:10
coderaashir: 2016-07-12 19:00:10

No need for long long, and I got AC while using cin/cout without sync_with_stdio(0)


Added by:Robert Rychcicki
Date:2009-01-10
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS OBJC PERL6 VB.NET