3036230_wa.c

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#define max 1000001
 
__int64 INF;

int N;
int a, b, c, d;

__int64 n[max], s[max], l[max];
__int64 dis[max][2];

int init()
{
	int i;
 
	scanf("%d",&N);
	if(N==0)
	{
		return 0;
	}
	scanf("%d%d%d%d",&a,&b,&c,&d);
	for(i = 0; i < N; ++i)
	{
		scanf("%I64d",&n[i]);
	}
	for(i = 0; i <= N; i++)
	{
		scanf("%I64d",&l[i]);
	}
	for(i = 0; i < N; i++)
	{
		scanf("%I64d",&s[i]);
	}
	return 1;
}

__int64 min(__int64 n1,__int64 n2)
{
	return n1 < n2 ? n1 : n2;
}

void solve()
{
	int t, i;
	__int64 ansl, ansr, tmp;

	if(b > d)
	{
		t = b;
		b = d;
		d = t;
		t = a;
		a = c;
		c = t;
	}
	ansl = l[b];
	tmp = 0;
	for(i = b-1; i >= 0; i--)
	{
		tmp += n[i]+s[i];
		if(tmp+l[i] < ansl)
		{
			ansl = tmp;
		}
	}
	ansr = l[d];
	tmp = 0;
	for(i = d+1; i <= N; i++)
	{
		tmp += n[i-1]+s[i-1];
		if(tmp+l[i] < ansr)
		{
			ansr = tmp;
		}
	}
	if(b==d)
	{
		printf("%I64d\n",ansl<ansr?ansl:ansr);
	}
	else
	{
		l[b] = ansl;
		l[d] = ansr;
		dis[b][a] = 0;
		dis[b][!a] = l[b];
		for(i = b+1; i <= d; i++)
		{
			dis[i][0] = min(dis[i-1][0]+n[i-1],dis[i-1][1]+s[i-1]+l[i]);
			dis[i][1] = min(dis[i-1][1]+s[i-1],dis[i-1][0]+n[i-1]+l[i]);
		}
		printf("%I64d\n",dis[d][c]);
	}
}

int main()
{
	while(init())
	{
		solve();
	}
	return 0;
}