網頁

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時間總合會越來越小。