题意：
有三个邮递员A,B,C
一开始分别在地点1,2,3(M<=200)，给定矩阵G，G[i][j]满足G[i][j]<=G[i][k]+G[k][j]，表示i到
j的代价，每天有一封邮件(共N<=1000)在第Ni个地点，需要派一个邮递员过去，不能有两个人在同一地点，每次只能移动一个人。
做
法：
出题人没有道德 这个题是CEOI2005的service
考虑朴素做法F[T][i][j][k]表示第T天，三个邮递员各在
i,j,k，转移即枚举哪个人去。
有个优化 规定i<j<k 可以优化一般。
但是这个复杂度是无法通过此题的
注意到
第i天必然有个人要去Ni，所以可以将F[T][i][j][k]减到F[i][j][k]表示第i天另外两个邮递员在j,k
最后规定
j<k，将i维滚动，便完成了此题。
（原题还要求输出方案 在64M内存情况下只能用unsigned
char记录方案，较恶心）
1 #include <cstdio>
2 #include <cstring>
3 int N,Q,G[205][205],list[1005];
4 int F[2][205][205];
5 inline void Update(int &u,int v)
6 {
7 if (u>v||u<0) u=v;
8 }
9 int main()
10 {
11 scanf("%d",&N);
12 for (int i=1;i<=N;++i)
13 for (int j=1;j<=N;++j)
14 scanf("%d",&G[i][j]);
15 for (;scanf("%d",&list[++Q])!=EOF;);
16 --Q;
17 memset(F[1],-1,sizeof(F[1]));
18 F[1][2][3]=G[1][list[1]];
19 F[1][1][3]=G[2][list[1]];
20 F[1][1][2]=G[3][list[1]];
21 for (int i=1,pre=1;i<Q;++i,pre^=1)
22 {
23 memset(F[pre^1],-1,sizeof(F[pre^1]));
24 for (int j=1;j<N;++j)
25 for (int k=j+1;k<=N;++k)
26 if (F[pre][j][k]>=0)
27 {
28 if (list[i+1]!=j&&list[i+1]!=k)
29 Update(F[pre^1][j][k],F[pre][j][k]+G[list[i]][list[i+1]]);
30 if (list[i+1]!=list[i]&&list[i+1]!=k)
31 if (k<list[i]) Update(F[pre^1][k][list[i]],F[pre][j][k]+G[j][list[i+1]]);
32 else Update(F[pre^1][list[i]][k],F[pre][j][k]+G[j][list[i+1]]);
33 if (list[i+1]!=list[i]&&list[i+1]!=j)
34 if (j<list[i]) Update(F[pre^1][j][list[i]],F[pre][j][k]+G[k][list[i+1]]);
35 else Update(F[pre^1][list[i]][j],F[pre][j][k]+G[k][list[i+1]]);
36 }
37 }
38 int ret=1<<30;
39 for (int i=1;i<N;++i)
40 for (int j=i+1;j<=N;++j)
41 if (F[Q&1][i][j]>=0)
42 Update(ret,F[Q&1][i][j]);
43 printf("%d\n",ret);
44 return 0;
45 }
46