作者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