TopCoder

餘切
$\Huge\text{freeh1}$

User's AC Ratio

100.0% (4/4)

Submission's AC Ratio

75.5% (37/49)

Tags

Description

$$\text{B8}=\text{B-eight} \approx \text{B-ate} = \text{Bate} \approx \text{Bait}$$
看完以上算式,你應該知道這題為什麼被稱作餌題了。
但你知道為什麼這題被叫做噁題嗎🙃?

事實是,我也不知道,但是有個 House Robber 是這樣說的:
「我的名字叫浩斯 · 拉伯,$25$ 歲。住在田丁町十字路的別墅區一帶,未婚。我在各鄰居的家中服務。每天都做深夜班,要五點才能回家。我不吸毒,但我天天都會喝鄰居家的溫牛奶。回家前,我一定會把門關上,然後跟警察比 $20$ 分鐘的賽跑,回了家,洗完澡,上了床,馬上熟睡。凌晨五點半入睡,每天要睡足十二個小時。一覺到下午,決不把疲勞和壓力留到晚上。即使如此,醫生都說我的作息很不正常。」

從他的自我介紹,可以看出他是一個和鄰居交流的好人。但是由於三更半夜拜訪鄰居容易壓縮到黃金睡眠時間,因此每次拜訪鄰居時他都會先規劃好路線,使得他去拜訪鄰居回家的時間*盡可能早*。

不過浩斯 · 拉伯遇到一個問題,那就是他現在很少成功在凌晨五點入睡,因為他不會使用 Dinitz 演算法,這樣每天睡眠不足的狀況困擾他已久,因此他找到了你希望這對你而言是個難度剛好的挑戰,使你能達到 flow 的心理狀態並回答這個問題。

浩斯 · 拉伯告訴你他每天都會晚上十一點(23:00)準時出門出發去「拜訪」他的其中一個特定鄰居,而每次的拜訪會花他一個小時的時間,請你幫他計算符合條件時他最早的回家時間。

Input Format

第一行有兩個整數 $n, m$,代表田丁町中有幾戶人家和連接這些人家的道路數量
第二行有兩個整數 $s, t$,代表浩斯 · 拉伯的家的編號以及他要拜訪的鄰居
接下來 $m$ 行會各有三個整數 $u, v, c$,代表通過 $u, v$ 兩戶人家的其中一條單向道路花費的時間為 $c$,以秒為單位。

Output Format

若浩斯 · 拉伯能在凌晨五點(05:00)前回到家,請輸出最佳方案回到家的時間,無條件捨去到分鐘位;若不行則輸出 So many sleepless nights where you were waiting up on me.

Sample Input 1

4 4
1 0
1 3 7
3 0 5
0 1 63
1 2 60

Sample Output 1

00:01

Sample Input 2

4 3
0 1
1 2 60
2 3 60
3 1 60

Sample Output 2

So many sleepless nights where you were waiting up on me.

Hints

你有聽過網路流

Problem Source

Subtasks

No. Testdata Range Score

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536
1 1000 65536 65536
2 1000 65536 65536
3 1000 65536 65536
4 1000 65536 65536
5 1000 65536 65536
6 1000 65536 65536
7 1000 65536 65536
8 1000 65536 65536
9 1000 65536 65536
10 1000 65536 65536
11 1000 65536 65536
12 1000 65536 65536
13 1000 65536 65536
14 1000 65536 65536
15 1000 65536 65536
16 1000 65536 65536
17 1000 65536 65536
18 1000 65536 65536
19 1000 65536 65536
20 1000 65536 65536
21 1000 65536 65536
22 1000 65536 65536
23 1000 65536 65536
24 1000 65536 65536
25 1000 65536 65536
26 1000 65536 65536
27 1000 65536 65536
28 1000 65536 65536
29 1000 65536 65536
30 1000 65536 65536
31 1000 65536 65536
32 1000 65536 65536
33 1000 65536 65536
34 1000 65536 65536
35 1000 65536 65536
36 1000 65536 65536
37 1000 65536 65536
38 1000 65536 65536
39 1000 65536 65536
40 1000 65536 65536
41 1000 65536 65536
42 1000 65536 65536
43 1000 65536 65536
44 1000 65536 65536
45 1000 65536 65536
46 1000 65536 65536
47 1000 65536 65536
48 1000 65536 65536
49 1000 65536 65536