记录编号	21537	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	移动服务	最终得分	100
用户昵称	ybh	是否通过	通过
代码语言	Pascal	运行时间	2.270 s
提交时间	2010-11-11 11:02:02	内存使用	0.58 MiB

{Mobile Service
 动态规划
 Author: yangbohua
 Time: 2010-11-11}

program service;
var
  f:array[0..1,0..201,0..201] of longint;
  c:array[0..201,0..201] of longint;
  n,m,t,i,j,ans,v,last,temp,h:longint;

begin
  assign(input,'service.in');
  reset(input);
  assign(output,'service.out');
  rewrite(output);

  readln(n,m);
  for i:=1 to n do
    for j:=1 to n do
      read(c[i,j]);
  f[0,1,2]:=1;
  last:=3;
  h:=0;
  for t:=1 to m do
  begin
    read(v);
    if v=last then continue;
    fillchar(f[1-h],sizeof(f[1-h]),0);
    for i:=1 to n-1 do
      for j:=i+1 to n do
        if f[h,i,j]>0 then
        begin
          if (i<>v) and (j<>v) then
          begin
            if i<last then
            begin
              if (f[h,i,j]+c[j,v]<f[1-h,i,last]) or (f[1-h,i,last]=0)
                then f[1-h,i,last]:=f[h,i,j]+c[j,v];
            end
            else
            begin
              if (f[h,i,j]+c[j,v]<f[1-h,last,i]) or (f[1-h,last,i]=0)
                then f[1-h,last,i]:=f[h,i,j]+c[j,v]
            end;
            if j<last then
            begin
              if (f[h,i,j]+c[i,v]<f[1-h,j,last]) or (f[1-h,j,last]=0)
                then f[1-h,j,last]:=f[h,i,j]+c[i,v]
            end
            else
            begin
              if (f[h,i,j]+c[i,v]<f[1-h,last,j]) or (f[1-h,last,j]=0)
                then f[1-h,last,j]:=f[h,i,j]+c[i,v]
            end;
            if (f[h,i,j]+c[last,v]<f[1-h,i,j]) or (f[1-h,i,j]=0)
              then f[1-h,i,j]:=f[h,i,j]+c[last,v];
          end
          else
          begin
            if i=v then
            begin
              if j<last then
              begin
                if (f[h,i,j]<f[1-h,j,last]) or (f[1-h,j,last]=0)
                  then f[1-h,j,last]:=f[h,i,j]
              end
              else
              begin
                if (f[h,i,j]<f[1-h,last,j]) or (f[1-h,last,j]=0)
                  then f[1-h,last,j]:=f[h,i,j]
              end
            end;
            if j=v then
            begin
              if i<last then
              begin
                if (f[h,i,j]<f[1-h,i,last]) or (f[1-h,i,last]=0)
                  then f[1-h,i,last]:=f[h,i,j]
              end
              else
              begin
                if (f[h,i,j]<f[1-h,last,i]) or (f[1-h,last,i]=0)
                  then f[1-h,last,i]:=f[h,i,j]
              end
            end;
          end;
        end;
    last:=v;
    h:=1-h;
  end;
  ans:=maxlongint;
  for i:=1 to n-1 do
    for j:=i+1 to n do
      if (f[h,i,j]>0) and (f[h,i,j]<ans) then ans:=f[h,i,j];
  writeln(ans-1);
  close(input);
  close(output);
end.