0 Judge
Code: 0
浦島太郎被帶到聾宮後,發現到處都是會讓他變老的機關,你可以幫幫他如何以最年輕的身體逃離聾宮嗎?聾宮是由$N$個房間所組成,有$M$條單向的道路連接這些房間,每條道路都設有機關,會改變浦島太郎的年齡;其中一個房間設有出口,可以離開聾宮。為了用最年幼的身體練習鐵沙掌,請問他離開聾宮時最少會老幾歲? 注意:就算走到了有出口的房間,也可以選擇要不要離開。
第一行有兩個數字$N,M$表示有$N$個房間,$M$條連接房間的單向道路,房間的編號為$0,1,2,...,N-1$,編號0號是浦島太郎一開始所在的房間,編號$N-1$號的房間有出口。接下來有$M$行,每行有三個整數(int)$A,B,C$表示間有一條從$A$房間到$B$房間的單向道路,通過它的時候會變老$C$歲(小於零的值代表變年輕)。 其中 $0\leq A,B\leq N-1, |C| \leq 10^6$
如果有辦法變年輕超過$10^{10000}$歲,請輸出hug hug
,如果沒有辦法走出聾宮,請輸出alone forever
,否則請輸出離開聾宮時最少會變老幾歲(如果是變年輕,請輸出負的值)。
4 6
0 1 1000
0 2 3
2 1 100
1 2 100
1 3 4
2 3 1000
107
5 5
0 1 1
1 2 -1
2 3 -1
3 1 -1
1 4 1
hug hug