You are given a directed graph with positive edge weights, a start point and an end point. Output the shortest path between the start point and the end point. Note that there may exist multiple edges in the graph, i.e. there may exist more than one edge from a vertex to another vertex. There may also exist self edges in the graph, i.e. edges with same incident vertices.
There are several test cases. Each test case starts with a number n (1<=n<=5000) and a number e, denoting the number of vertices and the number of edges respectively. Following are e lines, each with three numbers x, y and w (1<=w<=1000), denoting an edge x->y and its weight w. Finally there are two numbers at the end of each test case, denoting the start point and the end point. The vertex number starts with 1.
For each test case, output the shortest path weight on a line by itself. In case there’s no path from the start point to the end point, output -1.
2 1 1 2 3 1 2 3 2 1 2 1 2 3 1 1 3 3 1 1 2 1 1 3
3 2 -1
Migrated from old NTUJ.
| No. | Testdata Range | Score |
|---|