#include <stdio.h>
#include <iostream>
#include <fstream>
using namespace std;

#define INF 10000000

struct point{
	int x,y;
};
point start,end;

int n;
int dis[2][1000010];   //上下方i-1和i之间的距离
int between[1000010];  //上下方之间i之间的距离
__int64 cost[2][1000010];  //i，j点距离出发点的距离

int mark[2][1000010];

int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};


bool isbond(int x,int y){
	if(x>=0&&x<=1&&y>=0&&y<=n)return true;
	return false;
}

int getdis(int x1,int y1,int x2,int y2){
	if(x2!=x1)return between[y1];
	else{
		if(y2>y1)return dis[x1][y2];
		else return dis[x1][y1];
	}
}


void dijkstra(){
	int i,j,k;

	for(i=0;i<=1;i++){
		for(j=0;j<=n;j++){
			cost[i][j]=INF;
		}
	}

	mark[start.x][start.y]=1;
	int sx=start.x,sy=start.y;
	cost[sx][sy]=0;

	if(sx-1>=0)cost[sx-1][sy]=between[sy];
	if(sx+1<=1)cost[sx+1][sy]=between[sy];
	if(sy-1>=0)cost[sx][sy-1]=dis[sx][sy];
	if(sy+1<=n)cost[sx][sy+1]=dis[sx][sy+1];

	for(k=1;k<2*n;k++){
		if(mark[end.x][end.y]!=0)break;

		int min=INF;
		int minx=-1,miny=-1;
		for(i=0;i<=1;i++){
			for(j=0;j<=n;j++){
				if(cost[i][j]<min&&mark[i][j]==0){
					min=cost[i][j];
					minx=i;
					miny=j;
				}
			}
		}
		mark[minx][miny]=1;
		for(i=0;i<4;i++){
			int curx=minx+dx[i];
			int cury=miny+dy[i];

			if(isbond(curx,cury)&&mark[curx][cury]==0){
				if(cost[curx][cury]>cost[minx][miny]+getdis(minx,miny,curx,cury)){

					cost[curx][cury]=cost[minx][miny]+getdis(minx,miny,curx,cury);
				}
			}
		}

	}
	printf("%I64d\n",cost[end.x][end.y]);
}


void main(){
//	ifstream cin("data.txt");
//	freopen("data.txt","r",stdin);
	while(1){
		//cin>>n;
		scanf("%d",&n);
		if(n==0)break;
		memset(dis,0,sizeof(dis));
		memset(cost,0,sizeof(cost));
		memset(mark,0,sizeof(mark));

		//cin>>start.x>>start.y>>end.x>>end.y;
		scanf("%d%d%d%d",&start.x,&start.y,&end.x,&end.y);
		int i,j,k;

		for(i=1;i<=n;i++){
			//cin>>dis[0][i];
			scanf("%d",&dis[0][i]);
		}
		for(i=0;i<=n;i++){
			///cin>>between[i];
			scanf("%d",&between[i]);
		}
		for(i=1;i<=n;i++){
			//cin>>dis[1][i];
			scanf("%d",&dis[1][i]);
		}
		dijkstra();
		

	}
}

• 图很特殊，更好的算法是O(N)的DP (22) Dzx 2007-09-12 09:32:07
  • Dijkstra+Heap怎么会TLE啊 (3637) entrails 2007-09-16 22:27:40
    • Re:Dijkstra可以把这题水过去的 不需要把图显式得表示出来 (0) TheBeet 2007-09-17 00:00:44
• Re:我的dijkstra怎么老是超时，高手帮忙指点一下，谢谢！！！ (7) 1786263180 2019-07-26 16:23:34