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
a_h_ghaznavi: 2018-02-14 18:17:08

I have TIME-LIMIT!!!
why????

seyed37: 2018-01-11 09:31:47

SOAL BADIHI TOORE!

roham1381: 2018-01-11 09:30:17

badihi jat

shivan11: 2017-11-21 18:46:18

Last edit: 2017-11-21 19:18:22
vershwal: 2017-10-20 16:43:34

Last edit: 2017-10-20 16:44:36
edujtm: 2017-10-06 09:34:04

Graph is directed. The vertices starts their indexes from 1, not from 0 as said in the description ("all inputs range 0...10000").

anmoldua: 2017-09-18 21:32:11

AC in one go

deadpool_18: 2017-08-19 19:01:43

@mewtomat7 thanks brother :)

namitp: 2017-07-11 13:48:15

AC In one Go
(" - ")

ngtrthinh: 2017-06-10 13:28:40

:)

Last edit: 2017-06-11 16:22:58

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