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 |
dp,,额,,,,,,,,,,for(i=y1+1;i<=y2;i++) { __int64 temp=dpa; dpa=min(dpa+a[i],dpb+b[i]+c[i]); dpb=min(dpb+b[i],temp+a[i]+c[i]); } dpa->到河上点的最短路,,dpb->到河下点的最短路,, y1->起点,,y2->终点; a[i]->河上之间的时间,,b[i],,河下之间的时间,,,c[i]上下之间的时间.... dp之前需要修改c[y1]和c[y2],,,方法是向两边遍历寻找过河最小的时间..因为这个过程只可能 过一次河,,所以很好找,,,, Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator