[Home|Training|Problems|Contests|C Language] | [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 Input
The input consists of multiple test cases.The first line of each test case contains two integers A test case with 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 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).

Online Judge for ACM/ICPC

Processed in 1.5ms with 1 query(s).