题解疫情管控

louhao088 · 2022-02-19 15:07:09 · 个人记录

// Problem: U202296 疫情管控
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/U202296
// Memory Limit:  MB
// Time Limit:  ms
// 2022-02-19 14:35:27
// Author : louhao088
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
//static char buf[1000000],*p1=buf,*p2=buf;
//#define getchar() p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++
#define pi pair<int,int>
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid (l+r>>1)
#define lowbit (x&-x)
const int maxn=1e6,M=34005;
inline int read()
{
    char ch=getchar();bool f=0;int x=0;
    for(;!isdigit(ch);ch=getchar())if(ch=='-')f=1;
    for(;isdigit(ch);ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
    if(f==1)x=-x;return x;
}
inline void print(int x)
{
    static int a[55];int top=0;
    if(x<0) putchar('-'),x=-x;
    do{a[top++]=x%10,x/=10;}while(x);
    while(top) putchar(a[--top]+48);
}
int n,m,k,s,Ans[maxn],dis[maxn],F[maxn],t[maxn],tot=0,a,b,c,vis[maxn];
map<int,int>f[maxn],g[maxn];
priority_queue<pi>q;
vector<pi>e[maxn];
signed main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    n=read(),m=read(),k=read(),s=read();
    for(int i=1;i<=s;i++)
    {
        a=read(),b=read(),c=read();
        if(!f[b][c])f[b][c]=++tot;
        if(!g[a][b])g[a][b]=++tot,F[tot]=a;
        //cout<<f[b][c]<<" "<<g[a][b]<<endl;
        e[f[b][c]].pb(mp(g[a][b],0));e[g[a][b]].pb(mp(f[b][c],1));
    }
    memset(Ans,0x3f,sizeof Ans);memset(dis,0x3f,sizeof dis);
    for(int i=1;i<=n;i++)
    {
        //g[i][0]=++tot;
        int las=++tot;F[tot]=i;
        t[i]=read();if(t[i])q.push(mp(tot,0)),Ans[tot]=0,dis[tot]=0;
        for(auto j:g[i])
            e[las].pb(mp(j.se,0)),las=j.se;
    }
    while(!q.empty())
    {
        int x=q.top().fi;q.pop();
        if(vis[x])continue;vis[x]=1;
        if(F[x])Ans[F[x]]=min(Ans[F[x]],dis[x]);
        for(auto i:e[x])
            if(dis[i.fi]>dis[x]+i.se)
            {
                dis[i.fi]=dis[x]+i.se;
                q.push(mp(i.fi,-dis[i.fi]));
            }
    }
    for(int i=1;i<=n;i++)
        if(Ans[i]==0x3f3f3f3f)printf("-1 ");
        else printf("%d ",Ans[i]);
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
//static char buf[1000000],*p1=buf,*p2=buf;
//#define getchar() p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++
#define pi pair<int,int>
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid (l+r>>1)
#define lowbit(x) (x&-x)
const int maxn=1e5+5,M=34005;
inline int read()
{
    char ch=getchar();bool f=0;int x=0;
    for(;!isdigit(ch);ch=getchar())if(ch=='-')f=1;
    for(;isdigit(ch);ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
    if(f==1)x=-x;return x;
}
inline void print(int x)
{
    static int a[55];int top=0;
    if(x<0) putchar('-'),x=-x;
    do{a[top++]=x%10,x/=10;}while(x);
    while(top) putchar(a[--top]+48);
}
mt19937 rnd(time(0));
int n,m,s,k,a,b,c;
signed main()
{
    //freopen(".in","r",stdin);
    freopen(".in","w",stdout);
    n=300,m=300,k=300,s=3000;
    cout<<n<<" "<<m<<" "<<k<<" "<<s<<endl;
    for(int i=1;i<=s;i++)
    {
        a=rnd()%n+1;b=rnd()%m+1;c=rnd()%k+1;
        cout<<a<<" "<<b<<" "<<c<<endl;
    }
    for(int i=1;i<=n;i++)
    {
        a=rnd()%10;
        if(a)cout<<"0 ";else cout<<"1 ";
    }
    return 0;
}

/*********************************************************************
    作者:louhao088
    日期: 2022-02-19 15:09
*********************************************************************/