题面
一个公司有三个移动服务员，最初分别在位置1，2，3处。
如果某个位置（用一个整数表示）有一个请求，那么公司必须指派某名员工赶到那个地方去。
某一时刻只有一个员工能移动，且不允许在同样的位置出现两个员工。
从 p 到 q 移动一个员工，需要花费 c(p,q)。
这个函数不一定对称，但保证 c(p,p)=0。
给出N个请求，请求发生的位置分别为 p1~pN。
公司必须按顺序依次满足所有请求，且过程中不能去其他额外的位置，目标是最小化公司花费，请你帮忙计算这个最小花费。
输入格式
第1行有两个整数L,N，其中L是位置数量，N是请求数量，每个位置从1到L编号。
第2至L+1行每行包含L个非负整数，第i+1行的第j个数表示c(i,j) ，并且它小于2000。
最后一行包含N个整数，是请求列表。
一开始三个服务员分别在位置1，2，3。
输出格式
输出一个整数M，表示最小花费。
数据范围
3≤L≤200,
1≤N≤1000
输入样例：
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
输出样例：
5
思路
首先我们直接考虑四维数组dp，但看起来会炸，那么优化，我们其实可以压缩成为三维的，因为这三个邮递员里面必定有一个是等于当前的要求的地点，所以我们不用单独开一维去存。那么接下来我们考虑状态转移，这道题目我们发现从后往前推并不是很方便，所以我们考虑用当前状态去更新后面的状态，那么具体的转移就是枚举是哪个邮递员去了下一个地点，并且加上邻接矩阵里面的对应距离，就是下一个状态的值了。要记得不能有多个邮递员在同一地点的判断哦。
代码实现
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
#define rep(i,f_start,f_end) for (int i=f_start;i<=f_end;++i)
#define per(i,n,a) for (int i=n;i>=a;i--)
#define MT(x,i) memset(x,i,sizeof(x) )
#define rev(i,start,end) for (int i=0;i<end;i++)
#define inf 0x3f3f3f3f
#define mp(x,y) make_pair(x,y)
#define lowbit(x) (x&-x)
#define MOD 1000000007
#define exp 1e-8
#define N 1000005
#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int ,int> PII;
ll gcd (ll a,ll b) {return b?gcd (b,a%b):a; }
inline int read() {
char ch=getchar(); int x=0, f=1;
while(ch<'0'||ch>'9') {
if(ch=='-') f = -1;
ch=getchar();
}
while('0'<=ch&&ch<='9') {
x=x*10+ch-'0';
ch=getchar();
} return x*f;
}
const int maxn=201;
const int M=1010;
int f[M][maxn][maxn];
int maze[maxn][maxn];
int n,m;
int ask[M];
int main () {
cin>>n>>m;
rep (i,1,n)
rep (j,1,n) {
cin>>maze[i][j];
}
MT (ask,0);
rep (i,1,m) cin>>ask[i];
ask[0]=3;
int ans=0x3f3f3f3f;
MT (f,0x3f);
f[0][1][2]=0;
rev (i,0,m)
rep (x,1,n)
rep (y,1,n) {
int z=ask[i],u=ask[i+1],w=f[i][x][y];
if (x==y||y==z||x==z) continue;
f[i+1][x][y]=min (f[i+1][x][y],w+maze[z][u]);
f[i+1][x][z]=min (f[i+1][x][z],w+maze[y][u]);
f[i+1][z][y]=min (f[i+1][z][y],w+maze[x][u]);
}
rep (i,1,n)
rep (j,1,n) {
int z=ask[m];
if (i==j||j==z||z==i) continue;
ans=min (ans,f[m][i][j]);
}
cout<<ans<<endl;
return 0;
}