思路： dp[][][]代表考虑前i个请求，除了本位置之外的另外两个待在j和k这个位置，原本以为开4维然后发现。。有一维那个服务员的位置是确定的所以不用开，然后这个转移是常用的第二种转移方式，但注意服务员位置不能重复。 ac代码：
#include<bits/stdc++.h> using namespace std; const int N=1010,M=220; int f[N][M][M];//考虑前i个目前的服务员到达的是j倒数二个到达的是k int n,m; int c[M][M]; int l[N]; int res=1e9; int main() { cin >> n >> m; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>c[i][j]; for(int i=1;i<=m;i++) cin>>l[i]; memset(f,0x3f,sizeof f); for(int i=0;i<m;i++) for(int j=1;j<=n;j++) for(int k=1;k<=n;k++) { if(j==k) continue; if(!i) { if(l[1]!=1 && l[1]!=2) f[1][1][2]=min(f[1][1][2],0+c[3][l[1]]); if(l[1]!=1 && l[1]!=3) f[1][1][3]=min(f[1][1][3],0+c[2][l[1]]); if(l[1]!=2 && l[1]!=3) f[1][2][3]=min(f[1][2][3],0+c[1][l[1]]); continue; } if(l[i+1]!=j && l[i+1]!=k) f[i+1][j][k]=min(f[i+1][j][k],f[i][j][k]+c[l[i]][l[i+1]]); if(l[i+1]!=k &&l[i+1]!=l[i]) f[i+1][k][l[i]]=min(f[i+1][k][l[i]],f[i][j][k]+c[j][l[i+1]]); if(l[i+1]!=j &&l[i+1]!=l[i]) f[i+1][j][l[i]]=min(f[i+1][j][l[i]],f[i][j][k]+c[k][l[i+1]]); } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { res=min(res,f[m][i][j]); } cout<<res<<endl; }