描述 Description
一个公司有三个移动服务员。如果某个地方有一个请求，某个员工必须赶到那个地方去（那个地方没有其他员工），某一时刻只有一个员工能移动。被请求后，他才能移动，不允许在同样的位置出现两个员工。从 p 到 q 移动一个员工，需要花费 c(p,q)。这个函数没有必要对称，但是 c(p,p)=0。公司必须满足所有的请求。目标是最小化公司花费。
输入格式 InputFormat
第一行有两个整数 L,N(3<=L<=200, 1<=N<=1000)。L 是位置数；N 是请求数。每个位置从 1 到 L 编号。下 L 行每行包含 L 个非负整数。第 i+1 行的第 j 个数表示 c(i,j) ，并且它小于 2000。最后一行包含 N 个数，是请求列表。一开始三个服务员分别在位置 1，2，3。
输出格式 OutputFormat
一个数 M，表示最小服务花费。
样例输入 SampleInput
5 9
0 1 1 1 1
1 0 2 3 2
1 1 0 4 1
2 1 5 0 1
4 2 3 4 0
4 2 4 1 5 4 3 2 1
样例输出 SampleOutput
5
代码 Code
很容易想到四维动规，按照题目规定缩成三维，再用滚动数组优化。
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define inf 0x7fffffff
int f[2][1001][1001];
int a[1001][1001];
int q[1001];
int i,j,t,n,m,l,r,k,z,y,x;
int main()
{
scanf("%d%d",&l,&n);
for (i=1;i<=l;i++) for (j=1;j<=l;j++) scanf("%d",&a[i][j]);
for (t=0;t<=1;t++) for (i=0;i<=l;i++) for (j=0;j<=l;j++) f[t][i][j]=inf/2711;
for (i=1;i<=n;i++) scanf("%d",&q[i]);
f[0][1][2]=0;
q[0]=3;
for (t=0;t<n;t++)
{
for (i=1;i<=l;i++) for (j=1;j<=l;j++) f[(t+1)&1][i][j]=inf;
for (i=1;i<=l;i++) for (j=1;j<=l;j++)
{
f[(t+1)&1][i][j]=min(f[(t+1)&1][i][j],f[t&1][i][j]+a[q[t]][q[t+1]]);
f[(t+1)&1][i][q[t]]=min(f[(t+1)&1][i][q[t]],f[t&1][i][j]+a[j][q[t+1]]);
f[(t+1)&1][q[t]][j]=min(f[(t+1)&1][q[t]][j],f[t&1][i][j]+a[i][q[t+1]]);
}
}
z=inf;
for (i=1;i<=l;i++) for (j=1;j<=l;j++)
{
if (f[n&1][i][j]!=0) z=min(z,f[n&1][i][j]);
}
printf("%d\n",z);
return 0;
}