DD人物介紹 : https://zerojudge.tw/ShowProblem?problemid=f754
DD和紅林比玩撲克牌後，紅林仍不服輸，於是聰明的Goodscore(D團的一員，是外國人)就提出了一個有趣的遊戲：在一個迷宮中，有許多個箱子，DD和紅林的目標就是要將每個箱子裡的物品找到並將其交給Goodscore，先找到的人就獲勝。
不過，有些箱子有上鎖(不一定只有一個)，而其鑰匙則放在其他的箱子裡，他們得先取得鑰匙，開完箱子上所有的鎖，才能打開那個箱子(打開前也不可經過)。
Goodscore會再比賽開始前給他們各一張地圖，標示著有幾個箱子、幾哪條路可走、有上鎖的箱子所對應的鑰匙放在哪個箱子。
身為DD的同伴，請你運用你的聰明才智，告訴DD要走哪幾條路，以及總共要花多少時間。
另外，DD身為第二代D影，會在他開過的箱子裡放「飛D神苦無」，因此他可隨時使用「飛D神」，回到之前已開過的箱子，不會耗費額外時間。
上圖為兩範例的地圖
中圖為範例一的答案
下圖為範例二的答案
(A~F依序為1~6)
單筆輸入
輸入的第一行有四個整數N、M、W、S，代表有N個箱子、M個可走的路、W個鎖、起始位置在第S號箱子。(0<N<20、(N-1)<M<(N*(N-1)/2)、0≦W<(N*(N-1)/2)、1≦S≦N)
接下來M行，各有三個整數A、B、C，代表A走到B或B走到A要花C分鐘的時間。(1≦A, B≦N, 0<C≦1000)
在接下來W行，各有兩個整數K、L，代表L箱子上有一個鎖，對應的鑰匙在K箱子裡。(1≦K, L≦N)
輸出DD完成任務(保證可以完成)需花費的時間。
輸出DD走過的路程(提示:有N-1行) :
每行輸出兩整數i、j，代表DD從i走到j
(依i從小到大輸出，若i一樣則依j從小到大輸出)
(不是照走過的順序輸出!!)
6 9 1 5 1 2 1 1 4 4 3 5 4 6 3 5 5 6 7 2 5 2 4 2 4 5 1 3 4 5 4 4 1
16 2 1 3 6 5 2 5 3 5 4
6 9 2 1 1 2 1 1 4 4 3 5 4 6 3 5 5 6 7 2 5 2 4 2 4 5 1 3 4 5 4 2 5 4 2
16 1 2 1 4 2 5 3 6 5 3
公開 測資點#0 (33%): 1.0s , <1K
公開 測資點#1 (33%): 1.0s , <1K
公開 測資點#2 (34%): 1.0s , <1K
範例一(中圖):
從E出發
花2分鐘到B
飛D神回E
花4分鐘到D
飛D神到B
花1分鐘到A
飛D神到E
花4分鐘到C
花5分鐘到F
最少只需花16分鐘
| ID | User | Problem | Subject | Hit | Post Date |
|
沒有發現任何「解題報告」
|
|||||