0 Judge
Code: 0
你知道如果一張圖上有負環,求最短路徑會是超困難的問題嗎(NP-hard),為了拯救大家避免遇到負環,你能預先檢查如果從 $0$ 號點出發是否會遇到負環嗎?
僅有單筆測資
第一行有兩個數字 $n$, $m$ 表示有 $n$ 個點 $m$ 條邊。
接下來有 $m$ 行,每行有三個數字 $i,j,v$ ,表示有一條 單向 邊 $i$ 到 $j$ 權重是 $v$
圖可能有 自環 跟 重邊 。
如果從$0$號點出發會經過負環,請輸出 GG
,否則輸出 PPAP
。最後要換行
對於所有測資:
對於部分測資
3 3
0 1 1000
1 2 15
2 1 -42
GG
4 4
0 1 10
1 2 20
2 3 30
3 0 -60
PPAP