一个bfs的解法

虽然差点超时了

#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
#define L 205
#define N 1005
struct rec{int a,b,c;};
bool judge[N][L][L];
int f[N][L][L];
int cost[L][L];
int p[N];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    memset(f,INT_MAX-2000,sizeof f);
    int l,n;
    cin>>l>>n;
    for(int i=1;i<=l;i++)
        for(int j=1;j<=l;j++) cin>>cost[i][j];
    for(int i=1;i<=n;i++) cin>>p[i];
    f[0][2][3]=0;
    p[0]=1;
    n=unique(p,p+n+1)-p-1;
    queue<rec> bfs;
    bfs.push({0,2,3});
    int ans=INT_MAX;
    while(bfs.size())
    {
        rec temp=bfs.front();
        bfs.pop();
        int i=temp.a,x=temp.b,y=temp.c;
        if(judge[i][x][y]) continue;
        judge[i][x][y]=true;
        if(i==n)
        {
            ans=min(ans,f[i][x][y]);
            continue;
        }
        rec temp1={i+1,x,y};
        rec temp2={i+1,p[i],x};
        rec temp3={i+1,p[i],y};
        if(p[i]>x) swap(temp2.b,temp2.c);
        if(p[i]>y) swap(temp3.b,temp3.c);
        int &t=f[i][x][y];
        int &a=f[i+1][x][y];
        int &b=f[i+1][temp2.b][temp2.c];
        int &c=f[i+1][temp3.b][temp3.c];
        if(p[i+1]==x)
        {
            bfs.push(temp3);
            c=min(c,t);
            continue;
        }
        if(p[i+1]==y)
        {
            bfs.push(temp2);
            b=min(b,t);
            continue;
        }
        bfs.push(temp1);
        bfs.push(temp2);
        bfs.push(temp3);
        a=min(a,t+cost[p[i]][p[i+1]]);
        b=min(b,t+cost[y][p[i+1]]);
        c=min(c,t+cost[x][p[i+1]]);
    }
    cout<<ans;
}