记录编号	77077	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	移动服务	最终得分	100
用户昵称	Ezoi_XY	是否通过	通过
代码语言	Pascal	运行时间	1.699 s
提交时间	2013-11-01 09:22:29	内存使用	0.63 MiB

Program cog496;
    Var
        C:Array[1..200,1..200]Of Longint;
        F:Array[0..1,1..200,1..200]Of Longint;
        P:Array[1..1000]Of Longint;
        N,L,I,X,S,Y:Longint;
    Begin
        Assign(Input,'service.in');
        Assign(Output,'service.out');
        Reset(Input);
        Rewrite(Output);
        Readln(L,N);
        For X:=1 To L Do
            For Y:=1 To L Do
                Read(C[X,Y]);
        For I:=1 To N Do Read(P[I]);
        Fillchar(F[1],Sizeof(F[1]),$3F);
        F[1,1,2]:=C[3,P[1]];
        F[1,1,3]:=C[2,P[1]];
        F[1,2,3]:=C[1,P[1]];
        For I:=2 To N Do
            Begin
                Fillchar(F[I And 1],Sizeof(F[I And 1]),$3F);
                For X:=1 To L Do
                    For Y:=1 To L Do
                        Begin
                            If (Y<>P[I]) And (P[I-1]<>P[I]) And (F[I And 1,Y,P[I-1]]>F[I And 1 Xor 1,X,Y]+C[X,P[I]]) Then F[I And 1,Y,P[I-1]]:=F[I And 1 Xor 1,X,Y]+C[X,P[I]];
                            If (X<>P[I]) And (P[I-1]<>P[I]) And (F[I And 1,X,P[I-1]]>F[I And 1 Xor 1,X,Y]+C[Y,P[I]]) Then F[I And 1,X,P[I-1]]:=F[I And 1 Xor 1,X,Y]+C[Y,P[I]];
                            If (X<>P[I]) And (Y<>P[I]) And (F[I And 1,X,Y]>F[I And 1 Xor 1,X,Y]+C[P[I-1],P[I]]) Then F[I And 1,X,Y]:=F[I And 1 Xor 1,X,Y]+C[P[I-1],P[I]];
                        End;
            End;
        I:=N And 1;
        S:=Maxlongint;
        For X:=1 To L Do
            For Y:=1 To L Do
                If S>F[I,X,Y] Then S:=F[I,X,Y];
        Writeln(S);
        Close(Input);
        Close(Output);
    End.