maxl=200;
var c:array[1..maxl,1..maxl]of longint;
x:array[0..maxn]of longint;
f:array[0..1,1..maxl,1..maxl]of longint;
l,n,i,j,k,p,q,pr:longint;
function min(a,b:longint):longint;
begin
if a>b then exit(b)
else exit(a);
end;
begin
readln(l,n);
for i:=1 to l do
begin
for j:=1 to l do read(c[i,j]);
readln;
end;
fillchar(f,sizeof(f),$7f);
f[1,1,2]:=0; x[0]:=3;
p:=0; q:=1;
for k:=1 to n do
begin
read(x[k]);
for i:=1 to l-1 do
if not(x[k-1]=i) and not(x[k]=i) then
for j:=i+1 to l do
if not(x[k-1]=j) and not(x[k]=j) then
f[p,i,j]:=f[q,i,j]+c[x[k-1],x[k]];
for i:=1 to x[k-1]-1 do f[p,i,x[k-1]]:=2000000000;
for i:=x[k-1]+1 to l do f[p,x[k-1],i]:=2000000000;
for i:=1 to x[k-1]-1 do
if not(i=x[k]) then
begin
for j:=1 to i-1 do
if not(j=x[k-1]) then
f[p,i,x[k-1]]:=min(f[p,i,x[k-1]],f[q,j,i]+c[j,x[k]]);
for j:=i+1 to l do
if not(j=x[k-1]) then
f[p,i,x[k-1]]:=min(f[p,i,x[k-1]],f[q,i,j]+c[j,x[k]]);
end;
for i:=x[k-1]+1 to l do
if not(i=x[k]) then
begin
for j:=1 to i-1 do
if not(j=x[k-1]) then
f[p,x[k-1],i]:=min(f[p,x[k-1],i],f[q,j,i]+c[j,x[k]]);
for j:=i+1 to l do
if not(j=x[k-1]) then
f[p,x[k-1],i]:=min(f[p,x[k-1],i],f[q,i,j]+c[j,x[k]]);
end;
p:=p xor 1;
q:=q xor 1;
end;
pr:=maxlongint;
for i:=1 to l-1 do
if i<>x[k] then
for j:=i+1 to l do
if j<>x[k] then pr:=min(pr,f[q,i,j]);
writeln(pr);
end.
f[k,i,j,x[i]]=min(f[k-1,i,j]+c[x[i-1],x[i]])
f[k,i,x[i-1],x[i]]=min(f[k-1,i,j]+c[j,x[i]])
其中：
1.k表示步数,x[i]数组表示i步的位置
2.f数组中三个变量表示第i步时三个员工位置，根据“同一时刻不可以有多个人在同一地点”，需保证三个变量值不相等
复杂度为n*l^3
====完美的分割线====
1.第i步时三个员工位置必包括x[i],所以可降为两维
2.dp方程无后效性，可用滚动数组
3.第i步时两个员工的位置如（1,3）（3,1）会导致运算重复，我们可以使f[k,i,j]中i<j,减少1/2的运算量
4.注意初始化，本题的初始化和"f[i,j,k]三个变量值不相等"判断较难写，代码的初始化堪称完美，可参考学习
复杂度n*l^3/2 空间l^2*2，完美过100%数据
难度：noip提高组第二题
类型：典型的dp降维优化问题
又因为3个农民都是不可以位置重复，则a,b,c三个量总是单调的，则若一个时刻需求服务位置就最多只有两种决策
再随便剪一下枝...好像都不用这么复杂吧...