3377.cpp

Ferry lanes 计算在河的两岸运送包裹的最优路径

#include <stdio.h>

#define N 1000005

typedef struct
{
	long direction;
	long point;
}node;

__int64 str[2][N] = {0};
__int64 sum[N] = {0};
__int64 over[N] = {0};
__int64 l[N] = {0};


long main()
{
		
	long n,i,t; long  aa,bb;
	
	node start,end;/*定义起点终点结构*/

	scanf("%ld",&n);/*输入当前规模*/

	while(n)
	{
		scanf("%ld %ld %ld %ld",&start.direction,&start.point,&end.direction,&end.point);/*输入起点终点*/

		for(i = 0;i < n;i ++)
			scanf("%I64d",&str[0][i]);/*输入北面的码头间需要的时间*/

		for(i = 0;i <= n;i ++)
			scanf("%I64d",&over[i]);/*输入自西向东的过河所需要的时间*/
		
		for(i = 0;i < n;i ++)
			scanf("%I64d",&str[1][i]);/*输入南面的码头间需要的时间*/
		
		if(start.point > end.point)/*如果起点在终点的东面，交换起点和终点*/
		{
			t = start.direction;
			start.direction = end.direction;
			end.direction = t;

			t = start.point;
			start.point = end.point;
			end.point = t;
		}
		
		for(i = n - 1;;i --)/*将终点那条边替换为最短的*/
		{
			if(i < end.point)
				break;
			if(over[i] > over[i + 1] + str[0][i] + str[1][i])
				over[i] = over[i + 1] + str[0][i] + str[1][i];
		}
		for(i = 1;;i ++)/*将起点那条边替换为最短的*/
		{
			if(i > start.point)
				break;
			if(over[i] > over[i - 1] + str[0][i - 1] + str[1][i - 1])
				over[i] = over[i - 1] + str[0][i - 1] + str[1][i - 1];
		}

		i = start.point;
		l[i] = over[i];/*l[i]表示从起点开始到对岸的第i个码头所要的最短时间*/
		sum[i] = 0;/*sum[i]表示从起点开始到起点同岸的第i个码头所要的最短时间*/

		if(start.direction==0)
			aa=1;
		else  aa=0;
		if(start.direction==0)
			bb=0;
		else   bb=1;
		for(i = i + 1;i <= end.point;i ++)/*动态规划求sum[i],l[i]*/
		{
			l[i] = l[i - 1] + str[aa][i - 1];
			if(sum[i - 1] + str[bb][i - 1]+ over[i] < l[i])
				l[i] = sum[i - 1] + str[bb][i - 1]+ over[i];

			sum[i] = sum[i - 1] + str[bb][i - 1];
			if(l[i - 1] + str[aa][i - 1] + over[i] < sum[i])
				sum[i] = l[i - 1] + str[aa][i - 1] + over[i];
		}

		if(start.direction==end.direction)
		
		printf("%I64d\n",sum[end.point]);
		else
		printf("%I64d\n",l[end.point]);


		scanf("%ld",&n);
	}
	return 0;
}