| [Home|Training|Problems|Contests|C Language] | [Login|Register] |
|
Problems Status Rank |
Problem 1304
The least cost
Time Limit: 1000ms
Memory Limit: 65536kb Description
There is an undirected graph with V verticals and E edges. Can you find the least-cost path between source vertex S and destination vertex D according to the following rules? First, each edge has two costs A and B, and you have two skills named Skill-One and Skill-Two. When passing an edge, you can choose whether using skills or not. If you want to use skills when passing an edge, Skill-One or Skill-Two can be chosen (but can't choose both simultaneously). What's more, Skill-One (or Skill-Two) can be only used on one edge of the path at most. Skill-Two only can be used after Skill-One. More details about the two skills are as below: 1) Skill-One can help you to pass the edge by costing A/2 or B/2(such as 5/2=2). 2) Skill-Two can help you to pass the edge by costing A/3 or B/3(such as 5/3=1). If you do not want to use skills when passing an edge, the passing cost depends on the conditions of your using of past skill. More details as follows: 1) Paying A or B if Skill One and Skill Two both have been used before. 2) Paying A + B if Skill One and Skill Two neither have been used before. 3) Paying A if Skill One have been used and Skill Two have not been used before. Can you find the least cost between between S and D? Notice: As you know, there is no condition that Skill-Two is used but Skill-One has not been used. Input
The first line, an integer T, indicates number of test cases (T<=10). For each test case:The first line: four numbers V, E, S, D, indicating verticals, edges, source, and destination respectively. Each of the following E lines contains four numbers X, Y, A, B, indicating there exists an undirected edge with two costs A and B between vertex X and vertex Y. 2<=N<=1000, 1<=M<=2000, 1<=S, D<=N. 1<=X, Y<=N, X! =Y, 1<=A, B<=100. All numbers in the input are integers Output
For each test, output the least-cost path, or output "-1" if not existing a path connecting S and D directly or indirectly.
Sample Input
2 2 2 1 2 1 2 4 6 2 1 10 20 3 3 1 3 1 2 1 4 2 3 2 3 1 3 5 6 Sample Output
2 0 |