| ||||||||||
| 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