记录编号	21645	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	移动服务	最终得分	100
用户昵称	Des.	是否通过	通过
代码语言	Pascal	运行时间	0.976 s
提交时间	2010-11-12 08:59:28	内存使用	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.