Save Private Ryan - map building + voltage dp+deque+ shortest circuit

Topic link

#include <iostream>
#include <cstring>
#include <algorithm>
#include <set>
#include <deque>
#include <vector>
using namespace std;
#define x first
#define y second
typedef pair<int,int>PII;
const int N = 110,M = 1<<10;
vector<PII>g[N];
set<PII>edges;   // Judge whether the edge has been built in the figure 
int n,m,p,k;
int dist[N][M];  //  The first dimension is coordinates , The second dimension is the key state 
bool st[N][M];   // Judge whether it has been updated , If it is updated, it will be the minimum , There is no need to change 
int id[12][12];  // Map two dimensions to one dimension , Easy to write 
int key[N];      // Record the key of each position , In binary 
void build()
{
    
    int dx[4]={
    1,0,-1,0},dy[4]={
    0,1,0,-1};
    for(int i=1;i<=n;i++)
    {
    
        for(int j=1;j<=m;j++)
        {
    
            for(int u=0;u<4;u++)
            {
    
                int x=i+dx[u],y=j+dy[u];
                if(x<1||x>n||y<1||y>m)continue;
                int a=id[i][j],b=id[x][y];
                //  Build a map while walking that is not built in the map 
                if(!edges.count({
    a,b}))
                    g[a].push_back({
    b,0});
            }
        }
    }
}
int bfs()
{
    
    
    // deque ,
    memset(dist,0x3f,sizeof dist);
    deque<PII>q;
    q.push_back({
    1,0});
    dist[1][0]=0;
    
    while(q.size())
    {
    
        auto t=q.front();
        q.pop_front();
        if(st[t.x][t.y])continue;
        st[t.x][t.y]=true;
        if(t.x==n*m)return dist[t.x][t.y];
        // Pick up the key in this position 
        if(key[t.x])
        {
    
            int state=t.y|key[t.x];
            if(dist[t.x][state]>dist[t.x][t.y])
            {
    
                dist[t.x][state]=dist[t.x][t.y];
                q.push_front({
    t.x,state});
            }
        }
        for(auto [v,w] : g[t.x])
        {
    
            // If you need a key for the next position , But the last point is updated, and you can skip directly without this key 
            if(w&&!(t.y>>w-1&1))continue;
            if(dist[v][t.y]>dist[t.x][t.y]+1)
            {
    
                dist[v][t.y]=dist[t.x][t.y]+1;
                q.push_back({
    v,t.y});
            }
        }
    }
    
    return -1;
}

signed main()
{
    
    cin>>n>>m>>p>>k;
    for(int i=1,t=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            id[i][j]=t++;
    for(int i=1;i<=k;i++)
    {
    
        int x1,y1,x2,y2,c;
        cin>>x1>>y1>>x2>>y2>>c;
        int a=id[x1][y1],b=id[x2][y2];
        edges.insert({
    a,b});
        edges.insert({
    b,a});
        if(c)g[a].push_back({
    b,c}),g[b].push_back({
    a,c});
    }
    
    build();
    
    int s;
    cin>>s;
    while(s--)
    {
    
        int x1,y1,c;
        cin>>x1>>y1>>c;
        key[id[x1][y1]]|=1<<c-1;
    }
    cout<<bfs()<<endl;
}