很早就写过这个题目，那时候看题解写的，说白了就是抄的程序……

这几天又拿出来看，突然发现并没有想的那么难，大神勿喷……

用f[i,j,k]表示在第i个时刻的要求中，第一个人在j位置，第二个人在k位置时的最小花费，因为第三个人一定是在上一个时刻要求的位置，所以可以去掉表示第三个人位置的那一维，用req[i]表示第i时刻要求的位置，则在第i时刻，第三个人是在req[i-1]位置上，初始化需要注意。另外，要用滚动数组，否则会MLE

关于初始化：

f[1,1,2]=c[3,req[1]]

f[1,1,3]=c[2,req[1]]

f[1,2,3]=c[1,req[1]]  //c[i,j]为i移动到j的花费

其他的赋为max

仔细看看上面的初始化，其实就可以推导出状态转移方程

f[i,x1,x2]=min{f[i,x1,x2],f[i-1,x1,x2]+c[req[i-1],req[i]]}

f[i,x1,req[i-1]]=min{f[i,x1,req[i-1]],f[i-1,x1,x2]+c[x2,p[i]]}

f[i,x2,req[i-1]]=min{f[i,x2,req[i-1]],f[i-1,x1,x2]+c[x1,p[i]]}

 

[pascal 代码]

VAR        p:array[1..1000]of longint;        f:array[0..1,1..200,1..200]of longint;        c:array[1..200,1..200]of longint;        n,m,i,j,mins:longint;Procedure init; var        i,j:longint; begin        readln(n,m);        for i:=1 to n do                begin                        for j:=1 to n do read(c[i,j]);                        readln;                end;        for i:=1 to m do read(p[i]);readln;        fillchar(f,sizeof(f),$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]]; end;Function min(x,y:longint):longint; begin        if x