记录编号	38938	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	移动服务	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.538 s
提交时间	2012-06-27 20:49:02	内存使用	0.96 MiB

#include<iostream>
#include<cstdio>
using namespace std;
struct dptype{
	long s[201][201][2];
};
int main(){
	freopen("service.in","r",stdin);
	freopen("service.out","w",stdout);
	int l,n;//l位置n请求
	int request[1001]={2},c[201][201]={0};//2么......你懂得,c与题目意义同
	struct dptype f1,f2;
	scanf("%d%d",&l,&n);
	int i,j,k;
	for(i=1;i<=l;i++){
		for(j=1;j<=l;j++){
			scanf("%d",&c[i][j]);
			//cout<<c[i][j]<<endl;
		}
	}
	for(i=1;i<=n;i++) scanf("%d",&request[i]);//,cout<<request[i]<<endl;	
	for(i=1;i<=l;i++){
		for(j=1;j<=l;j++){
			f2.s[i][j][1]=0;
			f1.s[i][j][1]=-1;
		}
	}//struct就这点坏处...必须得蛋疼的赋初值......
	f1.s[1][3][0]=0;
	f1.s[1][3][1]=0;
	int x,y,z;
	long temp,jump;
	//cout<<n<<endl;
	//cout<<request[9]<<endl;
	for(i=1;i<=n;i++){
		//cout<<i<<endl;
		for(j=1;j<=l;j++){
			for(k=1;k<=l;k++){
				if(f1.s[j][k][1]==i-1){
					x=j,y=k,z=request[i-1],temp=f1.s[j][k][0],jump=request[i];
					//cout<<x<<" "<<y<<" "<<z<<" "<<temp<<endl;
					//cout<<i<<" "<<x<<" "<<request[i]<<" "<<c[x][request[i]]<<endl;
					//cout<<temp<<endl;
					if(y!=jump&&z!=jump&&(f2.s[y][z][1]!=i||temp+c[x][request[i]]<f2.s[y][z][0])){//挪x
						f2.s[y][z][1]=i;
						f2.s[y][z][0]=temp+c[x][request[i]];
						//cout<<f2.s[y][z][0]<<endl;
					}
					if(x!=jump&&z!=jump&&(f2.s[x][z][1]!=i||temp+c[y][request[i]]<f2.s[x][z][0])){//挪y
						f2.s[x][z][1]=i;
						f2.s[x][z][0]=temp+c[y][request[i]];
					}
					if(x!=jump&&y!=jump&&(f2.s[x][y][1]!=i||temp+c[z][request[i]]<f2.s[x][y][0])){//挪z
						f2.s[x][y][1]=i;
						f2.s[x][y][0]=temp+c[z][request[i]];
					}
					//cout<<f1.s[i][j][0]<<endl;
				}
			}
		}
		f1=f2;
		//cout<<f1.s[1][3][0]<<endl;
		/*for(int km=1;km<=l;km++){
			for(int lm=1;lm<=l;lm++){
				cout<<f1.s[km][lm][1]<<" ";
			}
			cout<<endl;
		}
		cout<<endl;*/
	}
	int answer=-1;
	for(i=1;i<=l;i++){
		for(j=1;j<=l;j++){
			if(f1.s[i][j][1]==n&&(answer==-1||f1.s[i][j][0]<answer)) answer=f1.s[i][j][0];
		}
	}
	printf("%d\n",answer);
	return 0;
}