增加一个起点S, 若某物品Ai的价格为Pi, 添一条权值为Pi的边S-->Ai
若物品Aj可以用Ai加优惠价Qi换得,加权值为Qi的边Ai-->Aj
除了S,每个点都有一个rank,枚举rank最大的点(从1到n),不妨设其rank值为R0,除去rank大于R0的,以及rank小于R0-m的.在剩余的图中求S到A1的最短路.
最短路(dijkstra)的时间复杂度是O(n^2),枚举n次,总的时间复杂度是O(n^3)

• 赞 (223) Honest 2006-03-15 21:29:33
• 应该是r0-m到r0+m范围内求最短路 (223) hansechang 2008-07-30 15:18:16
  • Re:应该是r0-m到r0+m范围内求最短路 (31) soarwind 2009-08-21 18:31:42
• Re:是我弱了 应该枚举rank的上界 (223) hansechang 2008-07-30 20:39:34
  • 你不弱哈，就是在r0-m 和r0+m间求，0msAC! 也不排除数据太弱 (0) threetree 2008-08-27 22:25:21
    • Re:你不弱哈，就是在r0-m 和r0+m间求，0msAC! 也不排除数据太弱 (0) kingwudy 2008-09-11 22:03:50
    • Re:你不弱哈，就是在r0-m 和r0+m间求，0msAC! 也不排除数据太弱 (13) zjx20 2008-11-21 20:12:58
• Re:请您稍稍详细的讲一下吧，因为我发现数据弱，有些dijkstra是错的能ac (235) zhzz 2008-10-03 23:27:14
• Re:请您稍稍详细的讲一下吧，因为我发现数据弱，有些dijkstra是错的能ac (42) watermoon 2009-03-18 09:15:33