tozangezan's diary

勝手にソースコードをコピペして利用しないでください。

PKU3377 Ferry Lanes

最大で折り返すのは2回です。ちゃんと向きとかも考えるとまわす回数は4回ですよね。(3回にしていた・・・)
この問題の最もクソなところは制約が怪しいところだと思う。答えがsigned-64bitに収まると言われてもinfすら決められないんだが…

#include<stdio.h>
#include<algorithm>
using namespace std;
typedef long long wolf;
wolf b[2][1100000];
wolf c[1100000];
wolf dp[2][1100000];
int main(){
	int a;
	while(scanf("%d",&a),a){
		int w,x,y,z;scanf("%d%d%d%d",&w,&x,&y,&z);
		for(int i=0;i<a;i++)scanf("%lld",&b[0][i]);
		for(int i=0;i<=a;i++)scanf("%lld",c+i);
		for(int i=0;i<a;i++)scanf("%lld",&b[1][i]);
		for(int i=0;i<=a;i++){
			dp[0][i]=dp[1][i]=(1LL<<61)-1;
		}
		dp[w][x]=0LL;
		for(int i=0;i<=a;i++){
			if(i)dp[0][i]=min(dp[0][i],dp[0][i-1]+b[0][i-1]);
			if(i)dp[1][i]=min(dp[1][i],dp[1][i-1]+b[1][i-1]);
			dp[0][i]=min(dp[0][i],dp[1][i]+c[i]);
			dp[1][i]=min(dp[1][i],dp[0][i]+c[i]);
		}
		for(int i=a;i>=0;i--){
			if(i<a)dp[0][i]=min(dp[0][i],dp[0][i+1]+b[0][i]);
			if(i<a)dp[1][i]=min(dp[1][i],dp[1][i+1]+b[1][i]);
			dp[0][i]=min(dp[0][i],dp[1][i]+c[i]);
			dp[1][i]=min(dp[1][i],dp[0][i]+c[i]);
		}
		for(int i=0;i<=a;i++){
			if(i)dp[0][i]=min(dp[0][i],dp[0][i-1]+b[0][i-1]);
			if(i)dp[1][i]=min(dp[1][i],dp[1][i-1]+b[1][i-1]);
			dp[0][i]=min(dp[0][i],dp[1][i]+c[i]);
			dp[1][i]=min(dp[1][i],dp[0][i]+c[i]);
		}
		for(int i=a;i>=0;i--){
			if(i<a)dp[0][i]=min(dp[0][i],dp[0][i+1]+b[0][i]);
			if(i<a)dp[1][i]=min(dp[1][i],dp[1][i+1]+b[1][i]);
			dp[0][i]=min(dp[0][i],dp[1][i]+c[i]);
			dp[1][i]=min(dp[1][i],dp[0][i]+c[i]);
		}
		printf("%lld\n",dp[y][z]);
	}
}