c262: 在巨人群中救回同伴是否搞錯了什麼
Tags : Floyd-Warshall
Accepted rate : 25人/28人 ( 89% ) [非即時]
評分方式:
Strictly

最近更新 : 2017-09-13 18:44

Content

以下防雷塊

-----------------------------------------------------------

阿爾敏:【糟了,米卡莎被帶走了】

艾連:【可惡!快追!】

因為一連串令人難過的事情

結果米卡莎被抓走了

所以 現在為了要討回米卡莎

必須穿越巨人群跑到米卡莎那邊

艾連:【把米卡莎(老婆)給我還來!!!】

 

經過了一番地獄般的追逐戰

最後....

請你算出米卡莎是否能被帶回來

----------------------------------------------------------

 為了迅速追到米卡莎

要利用巨人來快速移動

因為有些巨人非常兇猛

有些則是奇行種

如果途中遇到boss級巨人甚至會被吃掉

因此艾連將兩個巨人之間的移動危險度

和自身的能力值量化

只要自身能力值小於某次移動的危險值

就會成為食物

所以只有選擇最佳方法才有希望救到米卡莎

Input

每筆測資 第一行輸入 n(1<=n<=500)代表n個巨人,編號1~n

m(0<=m<=n*(n-1)/2)代表m筆資料

和 integer q 最大能力負荷

接下來m行資料

輸入a,b(1<=a,b<=n)代表巨人編號

和integer c 為巨人a和巨人b間移動的危險值

有時候數據會有bug 所以要以最後更新的資料為標準

輸出三個0結束

 

Output

假設米卡莎在巨人n 

艾連在巨人1

如果米卡莎得救輸出"Save"

不然輸出"GG"

Sample Input
7 3 70
3 2 50
1 3 60
2 7 120
7 3 130
3 2 50
1 3 60
2 7 120
0 0 0
Sample Output
GG
Save
測資資訊:
記憶體限制: 64 MB
不公開 測資點#0 (20%): 1.0s , <10M
不公開 測資點#1 (20%): 1.0s , <1K
不公開 測資點#2 (20%): 1.0s , <1K
不公開 測資點#3 (20%): 1.0s , <1K
不公開 測資點#4 (20%): 1.0s , <1K
Hint :
Tags:
Floyd-Warshall
出處:
106學年度板橋高中校內資訊學科能力競賽310573sao [管理者:
snail (蝸牛)
]


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