rt,感觉做法没问题,自己造的数据也能过,但是最后一个点T了

#include<cstdio>
#include<string.h>
#include<iostream>
using namespace std;
short l,n,c[201][201],aa[1001],op,op2;
int dp[2][201][201],ans=0x7fffffff;
string s[2][201][201];
struct node
{
	short a,b;
} p[2][201][201];
int x=0;
inline int read()
{
	char c=' ';
	x=0;
	while(!isdigit(c)) c=getchar();
	while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();
	return x;
}
signed main()
{
	l=read(),n=read();
	for(int i=1; i<=l; i++) for(int j=1; j<=l; j++) c[i][j]=read();
	for(int i=1; i<=n; i++) aa[i]=read();
	aa[0]=3;
	memset(dp[0],0x3f,sizeof dp[0]);
	dp[0][1][2]=dp[0][2][1]=0;
	p[0][1][2]=p[0][2][1]= {1,2};
	for(int i=0; i<n; i++)
	{
		op=(i&1),op2=op^1;
		memset(dp[op2],0x3f,sizeof(dp[op2]));
		for(int a=1; a<=l; a++)
			for(int b=1; b<=l; b++)
			{
				if(a==b||a==aa[i]||b==aa[i]) continue;
				if(dp[op][a][b]+c[aa[i]][aa[i+1]]<dp[op2][a][b])
				{
					dp[op2][a][b]=dp[op][a][b]+c[aa[i]][aa[i+1]];
					if(aa[i]==p[op][a][b].a) s[op2][a][b]=s[op][a][b]+"1",p[op2][a][b]= {aa[i+1],p[op][a][b].b};
					else if(aa[i]==p[op][a][b].b) s[op2][a][b]=s[op][a][b]+"2",p[op2][a][b]= {p[op][a][b].a,aa[i+1]};
					else s[op2][a][b]=s[op][a][b]+"3",p[op2][a][b]=p[op][a][b];
				}
				if(dp[op][a][b]+c[b][aa[i+1]]<dp[op2][a][aa[i]])
				{
					dp[op2][a][aa[i]]=dp[op][a][b]+c[b][aa[i+1]];
					if(b==p[op][a][b].a) s[op2][a][aa[i]]=s[op][a][b]+"1",p[op2][a][aa[i]]= {aa[i+1],p[op][a][b].b};
					else if(b==p[op][a][b].b) s[op2][a][aa[i]]=s[op][a][b]+"2",p[op2][a][aa[i]]= {p[op][a][b].a,aa[i+1]};
					else s[op2][a][aa[i]]=s[op][a][b]+"3",p[op2][a][aa[i]]=p[op][a][b];
				}
				if(dp[op][a][b]+c[a][aa[i+1]]<dp[op2][aa[i]][b])
				{
					dp[op2][aa[i]][b]=dp[op][a][b]+c[a][aa[i+1]];
					if(a==p[op][a][b].a) s[op2][aa[i]][b]=s[op][a][b]+"1",p[op2][aa[i]][b]= {aa[i+1],p[op][a][b].b};
					else if(a==p[op][a][b].b) s[op2][aa[i]][b]=s[op][a][b]+"2",p[op2][aa[i]][b]= {p[op][a][b].a,aa[i+1]};
					else s[op2][aa[i]][b]=s[op][a][b]+"3",p[op2][aa[i]][b]=p[op][a][b];
				}
			}
	}
	op=n&1;
	int a,b;
	for(int i=1; i<=l; i++) for(int j=1; j<=l; j++) if(dp[op][i][j]<ans) a=i,b=j,ans=dp[op][i][j];
	cout<<ans,putchar('\n');
	for(int i=0; i<n; i++) cout<<s[op][a][b][i],putchar(' ');
	return 0;
}