比赛 期末考试1 评测结果 AAAATEAETE
题目名称 Communication 最终得分 50
用户昵称 rzzakioi 运行时间 3.379 s
代码语言 C++ 内存使用 23.47 MiB
提交时间 2026-02-08 11:18:08
显示代码纯文本
#include<cstdio>
#include<queue>
#include<map>
#include<cstring>
#define int long long
#define pii pair<long long,long long>
using namespace std;
int n,l,r;
int to[2000005],nxt[2000005],val[2000005],h[2000005],cnt;
struct node{
    int x,y,w;
}a[500005];
void add(int u,int v,int w){
    to[++cnt]=v;
    val[cnt]=w;
    nxt[cnt]=h[u];
    h[u]=cnt;
}
priority_queue<pii,vector<pii>,greater<pii> >q;
int dis[500005];
bool vis[500005];
signed main(){
    freopen("tioj_communication.in","r",stdin);
    freopen("tioj_communication.out","w",stdout);
    scanf("%lld%lld%lld",&n,&l,&r);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i].x);
    }
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i].y);
    }
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i].w);
    }
    bool flag=1;
    for(int i=1;i<n;i++){
        if(a[i].x!=a[i+1].x)flag=0;
    }
    if(flag){
        for(int i=1;i<=n;i++){
            if(i==1)printf("%lld ",a[i].w);
            else{
                if(a[1].x+a[i].y>=l&&a[1].x+a[i].y<=r)printf("%lld ",a[1].w+a[i].w);
                else printf("-1 ");
            }
        }
        return 0;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(a[i].x+a[j].y>=l&&a[i].x+a[j].y<=r)add(i,j,a[j].w);
        }
    }
    memset(dis,0x3f,sizeof(dis));
    dis[1]=0;
    q.push(make_pair(0,1));
    while(!q.empty()){
        int u=q.top().second;
        q.pop();
        if(vis[u])continue;
        vis[u]=1;
        for(int i=h[u];i;i=nxt[i]){
            int v=to[i];
            if(dis[v]>dis[u]+val[i]){
                dis[v]=dis[u]+val[i];
                q.push(make_pair(dis[v],v));
            }
        }
    }
    for(int i=1;i<=n;i++){
        if(dis[i]==0x3f3f3f3f3f3f3f3f)printf("-1 ");
        else printf("%lld ",a[1].w+dis[i]);
    }
    return 0;
}