Programming學習筆記
網頁
首頁
UVa
POJ
2014年4月3日 星期四
UVa 10557 XYZZY
題意:
總共有N個節點(1~N),一開始起點在1且有100的能量,踏到每個節點都會有不同的能量變化(-100~+100),目標是要走到終點N且過程中能量不能歸0。
想法:
用SPFA演算法,不過要注意過程中可能會碰到正環或是負環,且有正環也不一定能走到終點,因為題目給的是單向的所以有可能走到正環的路走不到終點。因此可以假設如果走了100萬次(數字不一定)還是走不到終點就判定為無法到達。
沒有留言:
張貼留言
較新的文章
較舊的文章
首頁
訂閱:
張貼留言 (Atom)
沒有留言:
張貼留言