可能更优的空间复杂度，请问是否正确

/*
f[i][j][k]表示处理到 i 其余两人位置为 j,k
f[i][j][k]=min{f[i-1][j][k]+C(a[i-1],a[i])}
f[i][a[i-1]][k]=min{f[i-1][p][k]+C(p,a[i])}
f[i][j][a[i-1]]=min{f[i-1][j][p]+C(p,a[i])}
O(L^2)
发现只需要记录 f[i][a[i-1]][?]和 f[i][?][a[i-1]]的路径
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=1e18;
const ll L=205;
const ll N=1e3+5;
ll l,n,c[L][L],a[N],f[2][L][L],pre1[N][L],pre2[N][L];
struct Node{ll x,y,z;};
Node dfs(ll u,ll x,ll y)
{
	if (u==0) return (Node){1,2,3};
	Node res;
	if (x==a[u-1])
	{
		if (pre1[u][y])
		{
			res=dfs(u-1,pre1[u][y],y);
			swap(res.x,res.y);
		}
		else res=dfs(u-1,x,y);
	}
	else if (y==a[u-1])
	{
		if (pre2[u][x])
		{
			res=dfs(u-1,x,pre2[u][x]);
			swap(res.x,res.z);
		}
		else res=dfs(u-1,x,y);
	}
	else res=dfs(u-1,x,y);
	cout << res.x << ' ';
	return res;
}
int main()
{
	cin >> l >> n;
	for (int i=1;i<=l;i++)
		for (int j=1;j<=l;j++)
			cin >> c[i][j];
	for (int i=1;i<=n;i++) cin >> a[i];
	for (int j=1;j<=l;j++)
		for (int k=1;k<=l;k++)
			f[0][j][k]=INF;
	a[0]=1,f[0][2][3]=0;
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=l;j++)
			for (int k=1;k<=l;k++)
			{
				if (j==k||j==a[i]||k==a[i]) f[i&1][j][k]=INF;
				else f[i&1][j][k]=f[!(i&1)][j][k]+c[a[i-1]][a[i]];
			}
		if (a[i]==a[i-1]) continue;
		// f[i][a[i-1]][k]=min{f[i-1][p][k]+C(p,a[i])}
		for (int k=1;k<=l;k++)
		{
			if (k==a[i]) continue;
			for (int p=1;p<=l;p++)
			{
				if (p==k||p==a[i-1]) continue;
				if (f[i&1][a[i-1]][k]<=f[!(i&1)][p][k]+c[p][a[i]]) continue;
				f[i&1][a[i-1]][k]=f[!(i&1)][p][k]+c[p][a[i]],pre1[i][k]=p;
			}
		}
		// f[i][j][a[i-1]]=min{f[i-1][j][p]+C(p,a[i])}
		for (int j=1;j<=l;j++)
		{
			if (a[i]==j) continue;
			for (int p=1;p<=l;p++)
			{
				if (j==p||p==a[i-1]) continue;
				if (f[i&1][j][a[i-1]]<=f[!(i&1)][j][p]+c[p][a[i]]) continue;
				f[i&1][j][a[i-1]]=f[!(i&1)][j][p]+c[p][a[i]],pre2[i][j]=p;
			}
		}
	}
	ll ans=INF,x,y;
	for (int i=1;i<=l;i++)
		for (int j=1;j<=l;j++)
		{
			if (a[n]==i||a[n]==j||i==j||ans<=f[n&1][i][j]) continue;
			ans=f[n&1][i][j],x=i,y=j;
		}
	cout << ans << endl;
	dfs(n,x,y);
	return 0;
}