[請益] TWO Shortest Paths

[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


--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.116.82.205
推 PsMonkey:恩... 先說說你的想法吧... (純路人)
推 ericbibo:我試著用解10806的作法(max flow)去解
→ ericbibo:可是都被我找到反例給推翻了，所以想請教
→ ericbibo:大家的意見
推 march20:然後 weight 依然要一樣嗎?
推 ericbibo:兩條paths的weight不用一樣，可是weight
→ ericbibo:的和加起來要最小
推 march20:可以走到一樣的點, 但不能走相同的 edge
推 march20:是這樣嗎?
推 ericbibo:是的...你得到它了 ^_^
推 march20:有點懷疑這是 NP-hard problem