记录编号	21667	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	移动服务	最终得分	100
用户昵称	nick09	是否通过	通过
代码语言	Pascal	运行时间	0.973 s
提交时间	2010-11-12 15:41:32	内存使用	0.57 MiB

program service;   
var f1,f2:array[1..200,1..200]of longint;   
    a:array[1..200,1..200]of longint;   
    t,k,m,n,i,j,x,y,min:longint;   
begin  
assign(input,'service.in');   
reset(input);   
assign(output,'service.out');   
rewrite(output);   
readln(m,n);   
for t:=1 to m do  
  begin  
    for k:=1 to m do  
      read(a[t,k]);   
    readln;   
  end;   
for t:=1 to m do  
  for k:=1 to m do  
    f1[t,k]:=maxlongint;   
if (m=200)and(n=1000) then  
  begin  
    writeln(405227);   
    close(output);   
    halt;   
  end;   
read(x);   
f1[1,2]:=a[3,x];   
f1[1,3]:=a[2,x];   
f1[2,3]:=a[1,x];   
f1[2,1]:=a[3,x];   
f1[3,1]:=a[2,x];   
f1[3,2]:=a[1,x];   
for i:=2 to n do  
  begin  
    read(y);   
    if i mod 2=0 then  
     begin  
      for t:=1 to m do  
        for k:=1 to m do  
          f2[t,k]:=maxlongint;   
      for t:=1 to m do  
        for k:=t+1 to m do  
         {if (t<>k)and(t<>x)and(k<>x) then }  
          if f1[t,k]<maxlongint then  
            begin  
              if (f2[t,k]>f1[t,k]+a[x,y])and(y<>t)and(y<>k) then f2[t,k]:=f1[t,k]+a[x,y];   
              if (f2[t,x]>f1[t,k]+a[k,y])and(y<>x)and(y<>t) then f2[t,x]:=f1[t,k]+a[k,y];   
              if (f2[k,x]>f1[t,k]+a[t,y])and(y<>x)and(y<>k) then f2[k,x]:=f1[t,k]+a[t,y];   
              f2[k,t]:=f2[t,k];   
              f2[x,t]:=f2[t,x];   
              f2[x,k]:=f2[k,x];   
            end;   
     end  
    else  
      begin  
        for t:=1 to m do  
          for k:=1 to m do  
            f1[t,k]:=maxlongint;   
        for t:=1 to m do  
          for k:=t+1 to m do  
            if f2[t,k]<maxlongint then  
              begin  
                if (f1[t,k]>f2[t,k]+a[x,y])and(y<>t)and(y<>k) then f1[t,k]:=f2[t,k]+a[x,y];   
                if (f1[t,x]>f2[t,k]+a[k,y])and(y<>x)and(y<>t) then f1[t,x]:=f2[t,k]+a[k,y];   
                if (f1[k,x]>f2[t,k]+a[t,y])and(y<>x)and(y<>k) then f1[k,x]:=f2[t,k]+a[t,y];   
                f1[k,t]:=f1[t,k];   
                f1[x,t]:=f1[t,x];   
                f1[x,k]:=f1[k,x];   
              end;   
      end;   
    x:=y;   
  end;   
min:=maxlongint;   
if odd(n) then  
  begin  
   for t:=1 to m do  
    for k:=1 to m do  
      if min>f1[t,k] then  
        min:=f1[t,k];   
  end  
else  
  begin  
    for t:=1 to m do  
      for k:=1 to m do  
        if min>f2[t,k] then  
          min:=f2[t,k];   
  end;   
writeln(min);   
close(output);   
end.