Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

说说自己的几个思路

Posted by CSGrandeur at 2012-01-30 20:00:22 on Problem 1724 and last updated at 2012-01-30 20:03:53
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator