网易4.21普通技术笔试T3T4

#include<bits/stdc++.h>
using namespace std;
long long dp[100005][5];
int vis[100005];
struct node
{
    int x;
    int y;
    int z;
};
vector<node>q[100005];
void spfa(int x)
{
    queue<int>nh;
    nh.push(x);
    vis[x]=1;
    while(!nh.empty())
    {
        int now=nh.front();
        nh.pop();
        vis[now]=0;
        int len=q[now].size();
        for(int i=0; i<len; i++)
        {
            if(q[now][i].z==0)
            {
                int to=q[now][i].x;
                int val=q[now][i].y;
                if(dp[to][0]>dp[now][0]+val)
                {
                    dp[to][0]=dp[now][0]+val;
                    if(vis[to]=1)
                    {
                        nh.push(to);
                        vis[to]=1;
                    }
                }
                if(dp[to][1]>dp[now][1]+val)
                {
                    dp[to][1]=dp[now][1]+val;
                    if(vis[to]=1)
                    {
                        nh.push(to);
                        vis[to]=1;
                    }
                }
            }
            else
            {
                int to=q[now][i].x;
                int val=q[now][i].y;
                if(dp[to][1]>dp[now][0]+val)
                {
                    dp[to][1]=dp[now][0]+val;
                    if(vis[to]=1)
                    {
                        nh.push(to);
                        vis[to]=1;
                    }
                }
            }
        }
    }
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1; i<=m; i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        q[x].push_back({y,z,0});
        q[y].push_back({x,z,1});
    }
    for(int i=2; i<=n; i++)
    {
        dp[i][1]=1e18;
        dp[i][0]=1e18;
    }
    spfa(1);
    if(min(dp[n][0],dp[n][1])==1e18) printf("-1\n");
    else printf("%lld\n",min(dp[n][0],dp[n][1]));
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
int n,m,h;
int solve(int x,int y,int z)
{
    return (n*m)*(z-1)+(x-1)*m+y;
}
bool check(int x,int y,int z)
{
    if(x<=0||x>n) return 0;
    if(y<=0||y>m) return 0;
    if(z<=0||z>h) return 0;
    return 1;
}
int a[200005];
int now;
int fa[200005];
int nh[200005];
int modify[200005][5];
int vis[200005];
int dir[6][3]= {1,0,0,-1,0,0,0,1,0,0,-1,0,0,0,1,0,0,-1};
void dfs(int x,int y,int z,int num)
{
    vis[solve(x,y,z)]=1;
    fa[solve(x,y,z)]=num;
    for(int i=0; i<6; i++)
    {
        int xx=x+dir[i][0];
        int yy=y+dir[i][1];
        int zz=z+dir[i][2];
        if(check(xx,yy,zz)&&vis[solve(xx,yy,zz)]==0&&a[solve(xx,yy,zz)]==0)
        {
            dfs(xx,yy,zz,num);
        }
    }
    return ;
}
int f(int x)
{
    while(fa[x]!=x)
    {
        x=fa[x]=fa[fa[x]];
    }
    return x;
}
int main()
{
    scanf("%d%d%d",&n,&m,&h);
    for(int i=1; i<=n*m*h; i++)
    {
        fa[i]=i;
    }
    int k;
    scanf("%d",&k);
    for(int i=1; i<=k; i++)
    {
        scanf("%d%d%d",&modify[i][1],&modify[i][2],&modify[i][3]);
        if(a[solve(modify[i][1],modify[i][2],modify[i][3])]==1)
        {
            nh[i]=1;
        }
        a[solve(modify[i][1],modify[i][2],modify[i][3])]=1;
    }
    vector<int>ans;
    now=0;
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            for(int k=1; k<=h; k++)
            {
                if(vis[solve(i,j,k)]==0&&a[solve(i,j,k)]==0)
                {
                    dfs(i,j,k,solve(i,j,k));
                    now++;
                }
            }
        }
    }
    ans.push_back(now);
    for(int i=k; i>=2; i--)
    {
        if(nh[i]==1)
        {
            ans.push_back(now);
        }
        else
        {
            //printf("*********");
            a[solve(modify[i][1],modify[i][2],modify[i][3])]=0;
            vector<int>bza;
            for(int j=0; j<6; j++)
            {
                int xx=modify[i][1]+dir[j][0];
                int yy=modify[i][2]+dir[j][1];
                int zz=modify[i][3]+dir[j][2];
                if(check(xx,yy,zz)&&a[solve(xx,yy,zz)]==0)
                {
                    bza.push_back(f(solve(xx,yy,zz)));
                }
            }
            int len=bza.size();
            if(len==0) now++,fa[solve(modify[i][1],modify[i][2],modify[i][3])]=solve(modify[i][1],modify[i][2],modify[i][3]);
            else
            {
                map<int,int>q;
                for(int j=1; j<len; j++)
                {
                    if(q[bza[j]]==0&&bza[j]!=bza[0])
                    {
                        now--;
                        fa[bza[j]]=fa[bza[0]];
                        q[bza[j]]=1;
                    }
                }
                fa[solve(modify[i][1],modify[i][2],modify[i][3])]=bza[0];
            }
            ans.push_back(now);
        }
    }
    int len=ans.size();
    for(int i=len-1; i>=0; i--)
    {
        printf("%d\n",ans[i]);
    }
    return 0;
}