網頁

2014年4月3日 星期四

UVa 10557 XYZZY

題意:
    總共有N個節點(1~N),一開始起點在1且有100的能量,踏到每個節點都會有不同的能量變化(-100~+100),目標是要走到終點N且過程中能量不能歸0。
想法:
    用SPFA演算法,不過要注意過程中可能會碰到正環或是負環,且有正環也不一定能走到終點,因為題目給的是單向的所以有可能走到正環的路走不到終點。因此可以假設如果走了100萬次(數字不一定)還是走不到終點就判定為無法到達。



沒有留言:

張貼留言