作者changkh (留學生涯)
看板ck47th320
標題[問題] 再一個演算法的問題
時間Sat Apr 2 11:25:57 2005
又一個演算法的問題。最近快要被這些問題整慘了。
給一個undirected graph(V, E)。V是vertex，E是edge。
每一個edge有兩個weight，分別是WA和WB。
此外給定一個開始的vertex s,和一個結束的vertex t。
是否有演算法能找到一條從s到t的路徑，其中每一個vertex最多只
能經過一次。而且在這個路徑的每一個vertex上，如果把之前經過的edge
的WA和WB分別加起來，(sum WA) < (sum WB) +1？
這個演算法是P還是NP？如果這個問題是是NP，要如何證明？
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 68.43.196.35