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
hamobos_499: 2019-12-12 15:33:42

The graph is directed btw

gabirosa: 2019-12-03 02:54:36

tenso migos

hetp111: 2019-09-02 13:48:50

memset doesnt work for big value.... use fill() instead or a loop.

Last edit: 2019-09-02 13:50:56
adist98: 2019-08-14 11:57:52

Lazy Dijkstra will work here without any issues.

nayeem_joy: 2019-08-10 15:54:39

My solution here


tacongnam: 2019-06-06 04:47:35

What type of the graph? Is it directed / undirected or cycle graph?

amitjoshi: 2019-02-13 22:47:12

i want to submit a solution but then it asks me to sign in and then I can't submit the solution

Last edit: 2019-02-13 22:47:48
baby_doll: 2018-12-20 13:44:38

F[--edited--] of You need to mention whether the graph is directed or not
getting wrong answer again and again till not seeing comments what the f[--edited--] ...
f[--edited--] you problem creator...

=(Francky)=> Comment edited, and might be deleted. Please rephrase soon that to suit large audience. You're not here in a dirty bar !

Last edit: 2018-12-20 22:45:54
imabhinav: 2018-08-26 16:06:53

Take directed graph

lamia2658: 2018-04-11 12:38:15

dont make mistake by thinking the graph as undirected;

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