[請益] TWO Shortest Paths
看板Prob_Solve (計算數學 Problem Solving)作者ericbibo (^^)時間18年前 (2006/06/22 22:47)推噓8(8推 0噓 3→)留言11則, 3人參與討論串1/15 (看更多)
由於一直沒人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
推
06/22 22:55, , 1F
06/22 22:55, 1F
推
06/22 23:21, , 2F
06/22 23:21, 2F
→
06/22 23:22, , 3F
06/22 23:22, 3F
→
06/22 23:23, , 4F
06/22 23:23, 4F
推
06/22 23:42, , 5F
06/22 23:42, 5F
推
06/22 23:46, , 6F
06/22 23:46, 6F
→
06/22 23:46, , 7F
06/22 23:46, 7F
推
06/23 04:05, , 8F
06/23 04:05, 8F
推
06/23 04:05, , 9F
06/23 04:05, 9F
推
06/23 12:04, , 10F
06/23 12:04, 10F
推
06/24 14:07, , 11F
06/24 14:07, 11F
討論串 (同標題文章)
以下文章回應了本文 (最舊先)：
完整討論串 (本文為第 1 之 15 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章