C++ programing question24

Bellman-Ford Time Limit: 2 seconds

Problem Description For a directed graph G=( V, E ), edge e corresponds to a weight w, which can be regarded as the cost of taking this edge.

try to find the shortest path between two specific points on a directed weighted graph. Input File Format There will be a positive integer T at the beginning, which means that there will be T input datas. The first line of each input data has three positive integers n, m, and q, representing n points and m edges on the graph, 2 ? n ? 5000 , 1 ? m ? 20000, each point is numbered 0 ~ n-1, q is the number of queries. The next m rows each have three positive integers u, v, and w, which represent an edge from u to v with a weight of w, -1000 ? w ? 1000. Then there will be q rows of queries, each with two integers s and e, representing the shortest path from s to e. Output Format Each query outputs the answer in a separated line. If the shortest path does not exist (i.e. cannot be reached, there is a negative ring), the line outputs "No".

Example Sample Output 0 No 10 No No Sample Input 3 3 2 022 105 3 0-1 0 3 5 6 3 02 3 10 10 135 24-4 3 2-1 43-7 10 0 2 4 3 Example Sample Output 0 No 10 No No Sample Input 3 3 2 022 105 3 0-1 0 3 5 6 3 02 3 10 10 135 24-4 3 2-1 43-7 10 0 2 4 3