74. 浦島太郎

0 Judge

Code: 0


\( \newcommand{\ord}[1]{\mathcal{O}\left(#1\right)} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\floor}[1]{\lfloor #1 \rfloor} \newcommand{\ceil}[1]{\lceil #1 \rceil} \newcommand{\opord}{\operatorname{\mathcal{O}}} \newcommand{\argmax}{\operatorname{arg\,max}} \newcommand{\str}[1]{\texttt{"#1"}} \)

浦島太郎

題目敘述

浦島太郎被帶到聾宮後,發現到處都是會讓他變老的機關,你可以幫幫他如何以最年輕的身體逃離聾宮嗎?聾宮是由$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,否則請輸出離開聾宮時最少會變老幾歲(如果是變年輕,請輸出負的值)。

範例輸入1

4 6
0 1 1000
0 2 3
2 1 100
1 2 100
1 3 4
2 3 1000

範例輸出1

107

範例輸入2

5 5
0 1 1
1 2 -1
2 3 -1
3 1 -1
1 4 1

範例輸出2

hug hug

配分方法

  • 30% $1 \leq N \leq 100$, $1 \leq M \leq 1000$
  • 100% $1 \leq N \leq 1000$, $1 \leq M \leq 100000$

Hints

備註

我會抓抄襲 喔

Judge Setting

run-time limit: 1000 ms
memory limit: 65536000 byte
測資數量: 0