d792. 11463 - Commandos
Tags :
Accepted rate : 205人/220人 ( 93% ) [非即時]
評分方式:
Tolerant

最近更新 : 2010-09-21 13:21

Content

某個突擊隊收到了一個重要任務。他們要摧毀一個敵軍總部。該總部包含數棟由道路連接的大樓。突擊隊必須到每棟大樓的底部設置炸彈。他們從某一棟大樓的底部出發,再分散到各大數去。突擊隊員必須以既有的道路來往返於大樓之間。每個隊員都可以接連去好幾棟大樓,但任務完成後需要在一個共同的地點集合。題目會給你不同的敵軍總部的部署情況。你要確定完成任務所需的最短時間。設置炸彈的時間可以忽略,每個隊員所帶的炸彈數量沒有限制,任務所需的隊員數量也沒有限制。

Input

第一行有一個數字 T<50,代表測資筆數。每筆測資描述一個總部的部署。每筆測資的第一行有一個正整數 N≤100,表示總部的大樓數量。下一行有一個正整數 R,表示連接兩整大樓的道路的數量。接下來的 R 行每行有兩個相異的數字 0≤u,v<N,表示這條是連接 u, v 兩棟大樓。大樓的編號為 0 到 N-1。每筆測資的最後一行含有兩個整數 0≤s,d<N,s 表示任務的出發地點,d 則表示任務完成後的集合地點。

你可以假設兩棟大樓之間最多只有一條道路連接。所提供的測資保證可以從任一棟大樓到達另一棟大樓。

Output

對於每筆測資,要有一行輸出。該行包含測資編號及完成任務所需的最短時間。格式請參考輸出範例。 

Sample Input #1
2
4
3
0 1
2 1
1 3
0 3
2
1
0 1
1 0
Sample Output #1
Case 1: 4
Case 2: 1
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 1.0s , <1K
Hint :
Tags:
出處:
UVa11463 [管理者: snail (蝸牛) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」