Transformers' Mission

Time Limit: 4000/2000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Problem Description

A group of transformers whose leader is Optimus Prime(擎天柱) were assigned a mission: to destroy all Decepticon's(霸天虎) bases.

The bases are connected by roads. They must visit each base and place a bomb there. They start their mission at a particular base and from there they disseminate to reach each base.

The transformers must use the available roads to travel between bases. Any of them can visit one base after another, but they must all gather at a common base when their task in done because Optimus Prime(擎天柱) doesn't allow his teammate to run into any trouble.

Your job is to determine the minimum time needed to complete the mission.

You may assume that the time required to place a bomb is negligible.

Each transformer can carry unlimited number of bombs and there is an unlimited supply of transformers for this mission.


Input starts with an integer T(T ≤ 50), denoting the number of test cases.

The first line of each case starts with a positive integer n(1 ≤ n ≤ 1000), where n denotes the number of Decepticon's(霸天虎) bases.

The next line contains a positive integer m(0 ≤ m ≤ 100000), where m is the number of roads connecting two bases.

Each of the next m lines contain two distinct numbers u, v, w(0 ≤ u, v, w < n, u != v), this means there is a road from base u to base v which costs w units of time. The bases are numbered from 0 to n-1.

The last line of each case contains two integers s, e(0 ≤ s, e < n).

Where s denotes the base from where the mission starts and e denotes the base where they must meet.

You may assume that two bases will be directly connected by at most one road.

The input will be given such that, it will be possible to go from any base to another by using one or more roads.


For each case, output one line containing "Case #x: " followed by the minimum time.

Sample Input

5 6
0 1 2
1 2 2
3 1 2
4 0 3
3 2 3
3 4 1
4 3
5 5
1 0 1
1 2 3
1 3 3
4 2 2
3 4 1
4 2

Sample Output

Case #1: 7
Case #2: 9




Solved Number84
Submit Number141
Problem Tags
shortest paths
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^