试题分析
我们发现$dp(t,s1,s2,s3)$表示在$t$时刻$3$个人的位置。发现时间复杂度为$O(n \times L^3)$。不仅会$T$还会$MLE$，所以需要优化$dp$。我们发现当次$dp$合法时，肯定会有一项是到达的那个位置，所以可以优化掉一维。只需要把那个必须要经过的位置去掉，时间复杂度就变为$O(n \times L^2)$。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<climits>
using namespace std;
inline int read(){
int f=,ans=;char c=getchar();
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){ans=ans*+c-'';c=getchar();}
return f*ans;
}
const int N=;
const int L=;
int dp[N][L][L],val[L][L],n,l,p[N],minn=INT_MAX;
bool judge(int x1,int x2,int x3){
return (x1!=x2)&&(x2!=x3)&&(x1!=x3);
}
int _min(int a,int b){ return a>b?b:a;}
int main(){
l=read();n=read();
for(int i=;i<=l;i++)
for(int j=;j<=l;j++) val[i][j]=read();
memset(dp,/,sizeof(dp));dp[][][]=,dp[][][]=;p[]=;
for(int t=;t<=n;t++){
p[t]=read();
for(int i=;i<=l;i++){
for(int j=;j<=l;j++){
/*val[i][p]*/
if(judge(p[t],p[t-],j)){
dp[t][p[t-]][j]=_min(dp[t][p[t-]][j],dp[t-][i][j]+val[i][p[t]]);
dp[t][j][p[t-]]=_min(dp[t][p[t-]][j],dp[t][j][p[t-]]);
}
/*val[j][p]*/
if(judge(p[t-],i,p[t])){
dp[t][p[t-]][i]=_min(dp[t][p[t-]][i],dp[t-][i][j]+val[j][p[t]]);
dp[t][i][p[t-]]=_min(dp[t][p[t-]][i],dp[t][i][p[t-]]);
}
/*val[p[t-1]][p]*/
if(judge(i,j,p[t])){
dp[t][i][j]=_min(dp[t][i][j],dp[t-][i][j]+val[p[t-]][p[t]]);
dp[t][j][i]=_min(dp[t][j][i],dp[t][i][j]);
} }
}
}
for(int i=;i<=l;i++)
for(int j=;j<=l;j++) {
if(!(i!=j&&i!=p[n]&&j!=p[n])) continue;
minn=min(minn,dp[n][i][j]);
}
printf("%d",minn);
}