[Login|Register]
Problems

Status

Rank

Problem 1296
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
University of Science and Technology of China
Online Judge for ACM/ICPC
Processed in 1.3ms with 1 query(s).