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.


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.


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)


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


hide comments
ankushbbbr: 2016-04-05 19:19:28

getting a wrong answer with java

try2catch: 2016-02-12 08:47:11

1ST GO AC ! problem is a bitch! -_-

maxeinstle: 2016-02-02 06:59:17

Directed Graph!! Be Careful.

epsilon: 2016-01-24 14:16:59

stl rocks :)
my first dijkstra problem :)

Nguyen Cuong: 2016-01-03 08:58:31

my first dijkstra problem ^_^

sumit suthar: 2015-11-14 09:56:58

Take it eazy.. ;)

Karen: 2015-11-05 19:34:45

Graph is directed!
Use long long!!!

Last edit: 2015-11-05 19:35:22
vinod_10147: 2015-10-24 06:31:49

got AC in 0.00s

Nguyen Tung: 2015-10-13 18:16:34

Directed graph and the number of verticles might exceed 1000.
I got 2 SIGSEGV runtime errors while trying with maximum verticles = 200 and 500. Got AC with 10000.

harshit sharma: 2015-07-27 05:03:33

question should be more clear..

Added by:Robert Rychcicki
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)