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 117474335 at 2010-09-15 22:15:06 on Problem 3635 and last updated at 2010-09-16 00:21:46
设一个 money[1001][101] 表示 到点i时, 油量为j 的最小花费;
然后用dijstra的广搜变种来搜即可:
每次找一个最小花费点, if money[x][y + 1]满足, 拓展入队即可;
然后再更新x的邻点入队拓展即可;

dijstra的宽搜变种模板:
int d[] ; 
s入堆;
while (size) 
t = top() ; // 出堆;
if 找到终点v  return d[v] ;    
mark [t] = 1 ;标记;
拓展: if (! mark[p -> n] && d[ p -> n] > d[t] + p -> v )  入堆; 

return -1  ;    


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