[Login|Register]
Problems

Status

Rank

Problem 1280
Finding shortest path
Time Limit: 1000ms
Memory Limit: 65536kb
Description
I guess every contestant knows how to find a shortest path in a bidirectional graph, so this problem is intended to be a bit more difficult than that.

Given a bidirectional graph G=(V,E) with n vertices and m edges, it’s easy to find the shortest path between vertex S and T. Your task is to delete a set of edges with minimum cost, such that the shortest path in new graph is longer than the original one.

Input
The input consists of multiple test cases.

The first line of each test case contains two integers n and m, which specify the number of vertices and edges. (2 ≤ n ≤ 1000, 1 ≤ m ≤ 10000). The second line consists of two integer S and T, indicating the source and the sink. (1 ≤ S,Tn, ST) The next m lines each contains four integers ui, vi, wi and ci, indicating that there’s an edge between vertex ui and vi with length wi, and the cost of deleting it is ci. (1 ≤ ui,vin, 0 ≤ wi,ci ≤ 1000)

A test case with n=m=0 indicates the end of input.

Output
For each test case, output “Case x: ” first, where x is the case number. Then output the minimum cost to increase the length the shortest path between S and T. The cost is counted as the sum of deleted edges’ cost.

It is guaranteed that shortest path in initial graph always exists, and length of the shortest path between S and T is regarded as infinity if they are not connected.

Sample Input
2 3
1 2
1 2 2 3
1 2 2 4
1 2 3 5
4 5
1 4
1 2 1 1
2 3 1 1
3 4 1 1
1 4 3 2
2 2 2 3
4 5
2 3
1 2 3 2
2 4 3 4
1 3 2 3
3 4 2 3
1 4 0 1
0 0
Sample Output
Case 1: 7
Case 2: 3
Case 3: 6
University of Science and Technology of China
Online Judge for ACM/ICPC
Processed in 1.5ms with 1 query(s).