某個突擊隊收到了一個重要任務。他們要摧毀一個敵軍總部。該總部包含數棟由道路連接的大樓。突擊隊必須到每棟大樓的底部設置炸彈。他們從某一棟大樓的底部出發,再分散到各大數去。突擊隊員必須以既有的道路來往返於大樓之間。每個隊員都可以接連去好幾棟大樓,但任務完成後需要在一個共同的地點集合。題目會給你不同的敵軍總部的部署情況。你要確定完成任務所需的最短時間。設置炸彈的時間可以忽略,每個隊員所帶的炸彈數量沒有限制,任務所需的隊員數量也沒有限制。
第一行有一個數字 T<50,代表測資筆數。每筆測資描述一個總部的部署。每筆測資的第一行有一個正整數 N≤100,表示總部的大樓數量。下一行有一個正整數 R,表示連接兩整大樓的道路的數量。接下來的 R 行每行有兩個相異的數字 0≤u,v<N,表示這條是連接 u, v 兩棟大樓。大樓的編號為 0 到 N-1。每筆測資的最後一行含有兩個整數 0≤s,d<N,s 表示任務的出發地點,d 則表示任務完成後的集合地點。
你可以假設兩棟大樓之間最多只有一條道路連接。所提供的測資保證可以從任一棟大樓到達另一棟大樓。
對於每筆測資,要有一行輸出。該行包含測資編號及完成任務所需的最短時間。格式請參考輸出範例。
2 4 3 0 1 2 1 1 3 0 3 2 1 0 1 1 0
Case 1: 4 Case 2: 1
ID | User | Problem | Subject | Hit | Post Date |
沒有發現任何「解題報告」
|