TLE+MLE求调 || 悬赏20R

#include<bits/stdc++.h>
#define int long long
#define short unsigned short
#define rint unsigned int
#define mp make_pair
#define fi first
#define se second
#define lb lower_bound
#define fr front()
#define pii pair<short,rint>
#define N 65550
#define INF 1e9+7
#define INF2 1e18+7
using namespace std;

rint T,n,k,x,y,a[N],b[N],c[N],d[N],f[N],vis[N];
int dis[N];
vector<pii> g[N];
struct node{
    short u;int dis;
    friend bool operator<(node a,node b){
        return a.dis>b.dis;
    }
};
priority_queue<node> q;

void dijkstra(){
    while(!q.empty())q.pop();
    q.push({x,0});dis[x]=0;
    while(!q.empty()){
        int u=q.top().u;q.pop();
        if(vis[u])continue;vis[u]=1;
        for(auto i:g[u]){
            int v=i.fi,val=i.se;
            if(dis[v]>dis[u]+val&&u!=v){
                dis[v]=dis[u]+val;
                q.push({v,dis[v]});
            }
        }
    }
}

void find(int x,int s,int p){
    if(x==0)return;
    find((x-1)&p,s,p);
    int t=s|x;f[t]=c[t];
    for(int i=0;i<k;i++){
        if(t&(1<<i)){
            int to=t^(1<<i);
            if((to&s)==s)f[t]=min(f[t],f[to]);
        }
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin>>T;
    while(T--){
        cin>>n>>k>>x>>y;
        for(int i=0;i<(1<<k);i++){
            c[i]=INF,d[i]=INF,f[i]=INF;g[i].clear();vis[i]=0;
        }
        for(int i=1;i<=n;i++)cin>>a[i];
        for(int i=1;i<=n;i++)cin>>b[i];
        for(int i=1;i<=n;i++){
            rint cc;cin>>cc;
            c[a[i]]=min(c[a[i]],cc);
        }
        for(int i=1;i<=n;i++){
            rint dd;cin>>dd;
            d[b[i]]=min(d[b[i]],dd);
        }
        int cnt=0;
        for(int s=0;s<(1<<k);s++){
            f[s]=d[s];
            for(int now=s&(s-1);now>=0;now=(now-1)&s){
                f[now]=d[now];
                for(int i=0;i<k;i++){
                    if(!(now&(1<<i))){
                        int to=now|(1<<i);
                        if((to&s)==to)f[now]=min(f[now],f[to]);
                    }
                }
                if(now<=0)break;
            }
            for(int now=(s-1)&s;now>=0;now=(now-1)&s){
                int t=s^now;
                if(f[t]!=INF)g[now].push_back(mp(s,f[t])),cnt++;
                if(now<=0)break;
            }
        }
        for(int i=0;i<(1<<k);i++)f[i]=INF,dis[i]=INF2;
        for(int s=(1<<k)-1;s>=0;s--){
            f[s]=c[s];
            int x=((1<<k)-1)^s;
            find(x,s,x);
            for(int now=x;now>=0;now=(now-1)&x){
                int t=((1<<k)-1)^now;
                if(f[t]!=INF)g[s|now].push_back(mp(s,f[t]));
                if(now<=0)break;
            }
        }
        dijkstra();
        if(dis[y]>=INF2)cout<<-1;
        else cout<<dis[y];
        cout<<"\n";
        for(int i=0;i<(1<<k);i++){
            c[i]=INF,d[i]=INF,f[i]=INF;g[i].clear();vis[i]=0;
        }
    }
}