f869: D影的大冒險
Tags : DD 最小生成樹&拓樸排序
Accepted rate : 2人/2人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-05-24 11:04

Content

  DD人物介紹 : https://zerojudge.tw/ShowProblem?problemid=f754

DD和紅林比玩撲克牌後,紅林仍不服輸,於是聰明的Goodscore(D團的一員,是外國人)就提出了一個有趣的遊戲:在一個迷宮中,有許多個箱子,DD和紅林的目標就是要將每個箱子裡的物品找到並將其交給Goodscore,先找到的人就獲勝。

  不過,有些箱子有上鎖(不一定只有一個),而其鑰匙則放在其他的箱子裡,他們得先取得鑰匙,開完箱子上所有的鎖,才能打開那個箱子(打開前也不可經過)。

  Goodscore會再比賽開始前給他們各一張地圖,標示著有幾個箱子、幾哪條路可走、有上鎖的箱子所對應的鑰匙放在哪個箱子。

  身為DD的同伴,請你運用你的聰明才智,告訴DD要走哪幾條路,以及總共要花多少時間。

  另外,DD身為第二代D影,會在他開過的箱子裡放「飛D神苦無」,因此他可隨時使用「飛D神」,回到之前已開過的箱子,不會耗費額外時間。MST

上圖為兩範例的地圖

中圖為範例一的答案

下圖為範例二的答案

(A~F依序為1~6)

Input

單筆輸入

輸入的第一行有四個整數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)

Output

輸出DD完成任務(保證可以完成)需花費的時間。

輸出DD走過的路程(提示:有N-1行) :

每行輸出兩整數i、j,代表DD從i走到j

(依i從小到大輸出,若i一樣則依j從小到大輸出)

(不是照走過的順序輸出!!)

Sample Input #1
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 
Sample Output #1
16
2 1
3 6
5 2
5 3
5 4
Sample Input #2
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
Sample Output #2
16
1 4
1 2
2 5
3 6
5 3
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (33%): 1.0s , <1K
公開 測資點#1 (33%): 1.0s , <1K
公開 測資點#2 (34%): 1.0s , <1K
Hint :

範例一(中圖):

從E出發

花2分鐘到B

飛D神回E

花4分鐘到D

飛D神到B

花1分鐘到A

飛D神到E

花4分鐘到C

花5分鐘到F

最少只需花16分鐘

Tags:
DD 最小生成樹&拓樸排序
出處:
DD的奇幻冒險之旅 [管理者:
_xdddd ((找不到本用戶!))
]


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