Programming學習筆記
網頁
首頁
UVa
POJ
2014年3月29日 星期六
POJ 3259 Wormholes
題意:
FJ要找出是否能從某個起點出發,然後回到該起點但可以遇見出發時的自己,也就是時間和要<0。
題目N表示有幾個點
M表示有M行,每行S,E,T三個數字表示S點到E點或E點到S點所需要的時間是T
W表示有W行,每行S,E,T三個數字表示S點到E點所減少的時間T,也就是S到E你的時間總和會-T,注意這個是單向的,只有S點到E點
想法:
本題換句話說就是找出是否有負環(negative cycle),確認在所有路徑中是否存在一個cycle,使得一直走那個cycle時間總合會越來越小。
沒有留言:
張貼留言
較新的文章
較舊的文章
首頁
訂閱:
張貼留言 (Atom)
沒有留言:
張貼留言