Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

应该是r0-m到r0+m范围内求最短路

Posted by hansechang at 2008-07-30 15:18:16 on Problem 1062 and last updated at 2008-07-30 15:34:31
In Reply To:Re:请您稍稍详细的讲一下吧，因为我发现数据弱，有些dijkstra是错的能ac Posted by:xfxyjwf at 2006-03-15 21:26:41

> 增加一个起点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)

Followed by:

Re:应该是r0-m到r0+m范围内求最短路 (31) soarwind 2009-08-21 18:31:42

Post your reply here:

Home Page Go Back To top