b992.
欸肥宅快去運動啦!
內容
你是個成天待在家看動畫打遊戲的肥宅，但比其他肥宅幸運的是，你有一個天然可愛的幼馴染。有天你的幼馴染不知道發了什麼神經，堅持你要出門運動跑個幾圈，理由是擔心你以後會變成繭居尼特。你只好翻出你的地圖，找出裡面的$n$個路口和$m$條連接兩個路口的單向道路。對於第$i (1 \leq i \leq m)$條單向道路，你已經根據路況算出「跑完這段單向道路所消耗的大卡數」$c_i$。注意$c_i$可能小於$0$，代表單向道路$i$上有賣食物，讓你跑完後還變肥。由於你只是在敷衍你的幼馴染，並不想認真運動，你打算在這張地圖上找一個簡單環(亦即路口皆不重複的環)，使得跑完一圈所消耗的大卡數總和最小。
輸入說明
輸入的第一行是一個正整數$T$，代表接下來有$T$筆測試資料。
每筆測試資料的第一行有兩個整數$n, m$，代表地圖上有$n$個路口以及連接其中兩個路口的$m$條單向道路。
接下來的$m$行，第$i$行有三個整數$u_i, v_i, c_i$，代表有一條單向道路連接路口$u_i$到路口$v_i$，且沿著這條單向道路從路口$u_i$跑到路口$v_i$會消耗$c_i$大卡的熱量。
所有的測資檔皆滿足
- $T \leq 10$
- $1 \leq n \leq 5000$，$0 \leq m \leq 200000$，且$0 \leq mn \leq 10^8$
- $1 \leq u_i, v_i \leq n$，且$u_i \neq v_i$
- $-10^6 \leq c_i \leq 10^6$
輸出說明
對於每筆測試資料，輸出一行。如果地圖上根本沒有環，輸出"INF"(不含引號)。如果地圖上存在一個跑完後會讓你變肥的簡單環，輸出"-1"(不含引號)。如果地圖上存在簡單環，但沒有一個會讓你變肥，輸出一個非負整數$c^*$，代表跑完一個地圖上的簡單環，所消耗的熱量最小值。
範例輸入
#1
3 4 5 1 2 1 2 3 1 3 1 2 3 4 -1 4 1 4 3 3 1 3 -5 1 3 5 3 2 -10 4 3 1 2 -1 2 3 -1 3 2 -1
範例輸出
#1
4 INF -1
測資資訊：
記憶體限制：
512
MB
不公開 測資點#0 (80%): 10.0s , <10M
不公開 測資點#1 (20%): 1.0s , <10M
不公開 測資點#0 (80%): 10.0s , <10M
不公開 測資點#1 (20%): 1.0s , <10M
提示 ：
- 這題可以做到完美的$O(mn)$ 我也已經盡力讓$O(mn\log n)$的演算法TLE了
但如果最後你還是用$O(mn\log n)$的演算法AC 我也沒辦法了QAQ - 醒醒吧你沒有幼馴染
標籤:
出處:
經典問題
[管理者：
xavier13540
(柊 四千)
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
| 13116 | xavier13540 (柊 四千) | b992 | 1398 | 2017-12-11 05:49 |