你是國營地獄鐵路股份有限公司的發車員(簡稱地鐵公司),地鐵公司是一家很特別的鐵路公司,很多人都想臥軌自殺,因此地鐵公司列車造成的死亡事故遠高於其他鐵路公司,作為一名地鐵公司的發車員,你不但要負責發車的工作,決定每一趟列車行經的路線與發幾輛車,還要滿足這些想臥軌的人的心願。
地鐵公司有 $n$ 個車站與 $m$ 條鐵軌,每條鐵軌連接著兩個車站且只能單向通行,地鐵公司為了省錢,地鐵公司的鐵軌都偷工減料,對於每條鐵軌,都有自己的耐久度,每開過一輛列車都會使耐久度 -1,耐久度如果小於 0,鐵軌就會崩塌,同時每條鐵軌旁都有無限個人等著臥軌被撞,為了死的體面,他們比較喜歡一個一個被撞,也就是每一班車經過一條鐵軌只能撞死一個人,作為地獄列車發車員,你要盡可能的撞死更多人。
為了更高效率的計算今天可以撞多少人,請你寫一個程式計算今天最多可以撞死多少人。
第一行包含兩個整數 $n, m$,表示有 $n$ 個車站和 $m$ 條鐵軌。
對於每個車站,我們將其編號為 $1, 2, \ldots, n$,且車站 $1$ 是起始站,車站 $n$ 是終點站。每輛列車必須從起始站出發,開到終點站。
接下來的 $m$ 行描述了鐵軌的連接方式,每行包含三個整數 $a, b, c$,表示從 $a$ 站到 $b$ 站有一條耐久度為 $c$ 的鐵軌。
Constraints:
$1 \leq n \leq 500$
$1 \leq m \leq 1000$
$1 \leq a, b \leq n$
$1 \leq c \leq 10 ^ 9$
請輸出一個整數,代表今天最多可以撞死多少人
隨波逐流
No. | Testdata Range | Score |
---|