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
Prashant Gupta: 2012-09-23 07:56:34

i m getting SIGKILL plzz chk
mu submission id is 7707853
or i've this ideone link
http://ideone.com/FYumL

Prashant Gupta: 2012-09-23 07:52:08

i m getting SIGKILL plzz chk
mu submission id is 7707853

Panagiotis Kostopanagiotis: 2012-07-16 20:35:17

Is it possible that one node is connected to itself, it's the only thing i can come up with so my program doesn't output the correct answer all the time :/

Piyush Raman Srivastava: 2012-07-12 13:24:31

plz.. tell me why i am getting WA!
id: 7304181

Last edit: 2012-07-12 13:41:49
Tornike Mandzulashvili: 2012-01-27 15:19:28

why did i get TLE, i am using
t*(M log N) solution

axlrose: 2011-06-25 14:50:26

My solution returns the right solutions, but still keep getting the wrong answer, I wonder if it's reading with scanf () or write to printf (), please thanks.

Sarthak : 2011-04-09 13:13:28

is the given graph directed or non-directed ?? is A is always smaller than B ?
Reply(by naive_coder) : Directed graph. A may be greater than B.

Last edit: 2011-07-02 01:42:08
Jose Luis Castrillon Garrido: 2010-12-09 04:15:35

I just got AC using another alg, thank you for your suggestion, I would be honored if you sent to me some algs concerning graphs.

:D: 2010-12-07 15:38:09

You get WA because there are errors in your program :). Except admins/moderators and problem setter, no one can see your programs. If you want help, go to the forum and make a post the with your code pasted.

Last edit: 2010-12-07 15:38:44
Jose Luis Castrillon Garrido: 2010-12-07 06:52:40

my alg works ok but I dont know why I get WA I whish someone could help me.


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