$$\text{B8}=\text{B-eight} \approx \text{B-ate} = \text{Bate} \approx \text{Bait}$$
看完以上算式,你應該知道這題為什麼被稱作餌題了。
但你知道為什麼這題被叫做噁題嗎🙃?
事實是,我也不知道,但是有個 House Robber 是這樣說的:
「我的名字叫浩斯 · 拉伯,$25$ 歲。住在田丁町十字路的別墅區一帶,未婚。我在各鄰居的家中服務。每天都做深夜班,要五點才能回家。我不吸毒,但我天天都會喝鄰居家的溫牛奶。回家前,我一定會把門關上,然後跟警察比 $20$ 分鐘的賽跑,回了家,洗完澡,上了床,馬上熟睡。凌晨五點半入睡,每天要睡足十二個小時。一覺到下午,決不把疲勞和壓力留到晚上。即使如此,醫生都說我的作息很不正常。」
從他的自我介紹,可以看出他是一個和鄰居交流的好人。但是由於三更半夜拜訪鄰居容易壓縮到黃金睡眠時間,因此每次拜訪鄰居時他都會先規劃好路線,使得他去拜訪鄰居回家的時間*盡可能早*。
不過浩斯 · 拉伯遇到一個問題,那就是他現在很少成功在凌晨五點入睡,因為他不會使用 Dinitz 演算法,這樣每天睡眠不足的狀況困擾他已久,因此他找到了你希望這對你而言是個難度剛好的挑戰,使你能達到 flow 的心理狀態並回答這個問題。
浩斯 · 拉伯告訴你他每天都會晚上十一點(23:00)準時出門出發去「拜訪」他的其中一個特定鄰居,而每次的拜訪會花他一個小時的時間,請你幫他計算符合條件時他最早的回家時間。
第一行有兩個整數 $n, m$,代表田丁町中有幾戶人家和連接這些人家的道路數量
第二行有兩個整數 $s, t$,代表浩斯 · 拉伯的家的編號以及他要拜訪的鄰居
接下來 $m$ 行會各有三個整數 $u, v, c$,代表通過 $u, v$ 兩戶人家的其中一條單向道路花費的時間為 $c$,以秒為單位。
若浩斯 · 拉伯能在凌晨五點(05:00)前回到家,請輸出最佳方案回到家的時間,無條件捨去到分鐘位;若不行則輸出 So many sleepless nights where you were waiting up on me.