ACM/ICPC 之 DP解有规律的最短路问题(POJ3377)

//POJ3377
//DP解法-解有规律的最短路问题
//Time:1157Ms Memory:12440K
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std; #define MAXN 1000005 typedef long long LL; int n;
int dp[MAXN][3];
int sr, st, er, ed;
int main()
{
//freopen("in.txt", "r", stdin);
while(scanf("%d", &n), n)
{
scanf("%d%d%d%d", &sr,&st,&er,&ed);
if(st > ed)
{
swap(st, ed);
swap(sr, er);
}
for(int i = 1; i <= n; i++)
scanf("%d", &dp[i][0]);
for(int i = 0; i <= n; i++)
scanf("%d", &dp[i][2]);
for(int i = 1; i <= n; i++)
scanf("%d", &dp[i][1]); //更新st从左侧到达对岸的最短路
for(int i = st, w = 0; i > 0; i--)
{
w += dp[i][0] + dp[i][1]; //间接走陆路的路长和
dp[st][2] = min(dp[st][2], w + dp[i-1][2]);
if(w >= dp[st][2]) break;
} //更新ed从右侧到达对岸的最短路
for(int i = ed+1, w = 0; i <= n; i++)
{
w += dp[i][0] + dp[i][1];
dp[ed][2] = min(dp[ed][2], w + dp[i][2]);
if(w >= dp[ed][2]) break;
} LL dis[2];
dis[sr] = 0; //起始点右移最短路
dis[!sr] = dp[st][2]; //对岸右移最短路
for(int i = st + 1; i <= ed; i++)
{
int x = dp[i][sr], y = dp[i][!sr]; //该点与对岸到达右一点的路长
int z = dp[i][2]; //右侧水路长
LL tmp = dis[sr];
dis[sr] = min(dis[sr] + x, dis[!sr] + y + z);
dis[!sr] = min(dis[!sr] + y, tmp + x + z);
}
printf("%lld\n", dis[er]);
}
return 0;
}
上一篇:Node.js的内存问题


下一篇:openerp 报表字段 report_rml_content_data