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 |
说说自己的几个思路1、直接记忆化搜索DP,以dp[i][m](i是当前结点编号,m是剩余money)为状态记录到 终点的最短距离。532MS 2、以d[i][m]为状态点,以距起点距离越小剩余钱越多为优先级的优先级队列进行搜 索,以当前点的距离和已得到的最优解比较进行剪枝。94MS 3、以d[i]为状态点,但数组开d[i][m],对结点spfa,对“m”这一维进行类似背包的 DP。94MS 4、第一遍写的,有点四不像,而且不一定正确但是能AC:只设置一维的d[i]进行同2的 优先级搜索,类似spfa,增加数组mo[i],d[i]和mo[i]只在距离和钱都更优的情况下才 更新,也就是最终d[i]记录的不一定是距离最优解,最优解在出队时候另设变量更新。 0MS Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator