| [Home|Training|Problems|Contests|C Language] | [Login|Register] |
|
Problems Status Rank Statistics |
Problem G
Academic Report in USTC
Time Limit: 2000ms
Memory Limit: 65536kb Description
Dreamone has been studying in USTC for half a year. The hard-working of USTC students has impressed him deeply.Dreamone is fond of attending academic reports, which are held in USTC from time to time. As we know, there are many roads in the campus. See the map of USTC west campus below:  We assume that the academic reports are held on roads (strange, huh?). Here comes the problem: Given a start point S and an end point T, Dreamone wants to travel from S to T. At the same time, he wants to attend exactly K reports on the way from S to T. The problem is to find the shortest path from S to T. By the way, Dreamone can travel a road with an academic report more than once, Thus if he has passed a road with a report X times, the numbers of attended reports will be added by X. Input
The first line of the input file contains a single integer T (1 ≤ T ≤ 200), the number of test cases, followed by the input data for each test case. For each test case, The first line consists of three integers N (1<=N<=100) and M (1<=M<=1000), K (1<=K<=10) . N indicates the numbers of vertices of the map, M indicates the numbers of roads. Vertices are numbered from 1 to N. The next M lines each contain the information of road. Each road is described as follows: ‘U V C B’. U and V represent the two vertices of a road. C represents the length of the road. All the roads here are bidirectional. B represents whether there exists a report on the road, 1 indicates yes, 0 indicates no. (1<=U, V<=N, 0<C<=100, B=0 or 1) The next line contains two numbers: S and T. (1<=S, T<=N), which represent the start point and the end point respectively. Output
Output such shortest path from S to T. if there is not such path ,output -1 instead.
Sample Input
6 2 1 1 2 1 5 1 1 2 2 3 2 1 2 5 1 1 2 4 1 1 1 2 1 1 2 2 1 3 1 2 2 1 1 2 2 1 2 1 2 2 1 1 2 3 2 1 2 1 3 0 2 3 2 1 1 3 3 2 3 2 1 3 0 2 3 2 1 1 3 Sample Output
5 6 6 -1 5 9 Source
Wenhong@USTC
|