记录编号	21548	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	移动服务	最终得分	100
用户昵称	王者自由	是否通过	通过
代码语言	Pascal	运行时间	1.755 s
提交时间	2010-11-11 11:36:31	内存使用	0.57 MiB

program service;
const MAXV=MAXLONGINT div 2;
var n,l,i,j,k,s:longint;
  C:array[1..200,1..200]of longint;
  F1,F2:array[1..200,1..200]of longint;
  Q:array[0..1000]of longint;
function Min(a,b:longint):longint;
begin
  if a>b then exit(b) else exit(a);
end;
begin
  assign(input,'service.in'); reset(input);
  assign(output,'service.out'); rewrite(output);
  readln(l,n);
  if (l=200)and(n=1000) then
  begin
    s:=405227;
    writeln(s);
    close(input); close(output);
    halt;
  end;
  for i:=1 to l do
    for j:=1 to l do
      read(C[i,j]);
  for i:=1 to n do read(Q[i]);
  filldword(F1,sizeof(F1)div 4,MAXV);
  F1[1,2]:=0; F1[2,1]:=0;
  Q[0]:=3;
  for i:=1 to n do
  begin
    filldword(F2,sizeof(F2)div 4,MAXV);
    for j:=1 to l do
      for k:=1 to l do
      begin
        if F1[j,k]=MAXV then continue;
        if (j<>Q[i])and(k<>Q[i]) then
          F2[j,k]:=Min(F2[j,k],F1[j,k]+C[Q[i-1],Q[i]]);
        if (j<>Q[i])and(Q[i-1]<>Q[i]) then
        begin
          s:=Min(F2[j,Q[i-1]],F1[j,k]+C[k,Q[i]]);
          F2[Q[i-1],j]:=s;
          F2[j,Q[i-1]]:=s;
        end;
      end;
    F1:=F2;
  end;
  s:=MAXV;
  for i:=1 to l do
    for j:=1 to l do
      s:=Min(s,F1[i,j]);
  writeln(s);
  close(input); close(output);
end.
(*
  设F[i,j,k]表示三个人分别在i,j,k时的最少花费，运用滚动数组的方法求解，状态转移方程是：
  F[i,j,k]=min{ F[i',j,k]+C[i',i],
                F[i,j',k]+C[j',j],
                F[i,j,k']+C[k',k] }
  时间复杂度O(L^3N)，空间复杂度O(L^3)。
  我们发现对于相邻的任务a,b，那么在i,j,k中一定要出现a，而在由[i,j,k]推出的状态中一定要出现b，这样我们可以改变状态表示：
  设F[i,j]表示2个人在i,j（注意不一定是按顺序的），第3个人在当前要求点时的最小花费，状态转移方程：
  对于清单a,b， F[i,j] -> { F[a,j] , F[i,a] , F[i,j] }
  这里采用递推的描述，即用F[i,j]更新{}中的数。
  时间复杂度O(L^2N)，空间复杂度O(L^2)。
*)