EZDIJKST - Easy Dijkstra Problem
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)
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
What type of the graph? Is it directed / undirected or cycle graph?
i want to submit a solution but then it asks me to sign in and then I can't submit the solutionLast edit: 2019-02-13 22:47:48
F[--edited--] of You need to mention whether the graph is directed or not
Take directed graph
dont make mistake by thinking the graph as undirected;
looks like the graph is directed!
I have TIME-LIMIT!!!
SOAL BADIHI TOORE!
Last edit: 2017-11-21 19:18:22