记录编号	21488	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	496.移动服务	最终得分	100
用户昵称	郭乾乐	是否通过	通过
代码语言	C++	运行时间	1.320 s
提交时间	2010-11-11 08:11:40	内存使用	0.65 MiB

#include<iostream>
#include<fstream>
using namespace std;
int f[2][202][202];
int main()
{
	ifstream fin("service.in");
	ofstream fout("service.out");
	int a[201][201],l,n,i,j,k,r,w,lw;
	fin>>l>>n;
	for(i=1;i<=l;i++)
		for(j=1;j<=l;j++)
		{
			for(k=1;k<=2;k++)
				f[k&1][i][j]=9999999;
		    fin>>a[i][j];
		}
	fin>>w;
	f[1][1][2]=a[3][w];
	f[1][2][3]=a[1][w];
	f[1][1][3]=a[2][w];
	lw=w;
	for(i=1;i<n;i++)
	{
		fin>>w;
		for(j=1;j<=l;j++)
			for(k=1;k<=l;k++)
			{
				if(f[(i)&1][j][k]!=9999999&&j!=k&&k!=lw&&j!=lw)
				{
					if(f[(i+1)&1][j][k]>(f[i&1][j][k]+a[lw][w]))  f[(i+1)&1][j][k]=f[i&1][j][k]+a[lw][w];
					if(f[(i+1)&1][k][lw]>(f[i&1][j][k]+a[j][w]))  f[(i+1)&1][k][lw]=f[i&1][j][k]+a[j][w];
					if(f[(i+1)&1][j][lw]>(f[i&1][j][k]+a[k][w]))  f[(i+1)&1][j][lw]=f[i&1][j][k]+a[k][w];
				}
				f[(i)&1][j][k]=9999999;
			}
		lw=w;
	}
    r=117777790;
	for(i=1;i<=l;i++)
		for(j=1;j<=l;j++)
			if(f[n&1][i][j]!=0&&f[n&1][i][j]<r&&w!=i&&i!=j&&w!=j)
				r=f[n&1][i][j];
	fout<<r;
	return 0;
}