?

//POJ3377 //DP解法-解有規律的最短路問題 //Time:1157Ms Memory:12440K #include<iostream> #include<cstring> #include<cstdio> using namespace std;#define MAXN 1000005typedef 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; }

?

轉載于:https://www.cnblogs.com/Inkblots/p/5735753.html

總結

以上是生活随笔為你收集整理的ACM/ICPC 之 DP解有规律的最短路问题(POJ3377)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。