※ 引述《ericbibo (^^)》之銘言： : 由於一直沒人po文，所以我先po個已經困擾我很久的問題。 : 希望能吸引一點人氣。 (但願不會造成反效果...囧rz) : 在ACM Problem 10806中，( http://acm.uva.es/p/v108/10806.html ) : 我們必須從給定的起點 S 到終點 T 中， : 找 "兩條" 沒有重疊的minimum weight shortest paths。 : (也就是這兩條paths沒有經過相同的edges，且total weight值最小。) : 可是，假如我現在把題目改成: : 找"兩條"沒有重疊的minimum weight shortest paths， : 一條由給定的起點 S1 到終點 D1， : 另一條由起點 S2 到終點 D2 的話， : 有沒有什麼方法可以解決這個問題呢? : 我已經想這個問題好幾天了， : 希望高手能不吝指教一下~ XD 我也來賺賭本.. 如果我沒記錯的話 好像是這樣: 先找 S 到 T 的最短路徑, 假設是 cost1, 然後把這條最短路徑的方向反向, weight 變負的 (就是 max flow 那樣算 residual network) 然後再找 T 到 S 的最短路徑 cost2, 然後 cost1 + cost2 就是答案~ 求最短路徑的方法可用 Dijkstra 還是偷懶用 Floyd Washall.. 因為雖然會有 negative edge 但是不會有 negative cycle, 所以可以安心的用 @@: 有錯請指教 m(_ _)m -- 全賭法國隊了...orz --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.115.205.19