比赛 期末考试1 评测结果 AAAATETETT
题目名称 Communication 最终得分 40
用户昵称 小福鑫 运行时间 5.647 s
代码语言 C++ 内存使用 89.26 MiB
提交时间 2026-02-08 11:00:41
显示代码纯文本
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,L,R,a[1000001],b[1000001],w[1000001],m,s,u,k,v,dis[5000001],to[5000001],nxt[5000001],h[5000001],val[5000001],cnt;
bool g[5000001];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
void add(int a,int b,int c){
	to[++cnt]=b;
	val[cnt]=c;
	nxt[cnt]=h[a];
	h[a]=cnt;
}
signed main(){
    freopen("tioj_communication.in","r",stdin);
    freopen("tioj_communication.out","w",stdout);
	cin>>n>>L>>R;
	for(int i=0;i<=n;i++){
		dis[i]=1e15;
	}
	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++){
        cin>>w[i];
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(a[i]+b[j]>=L&&a[i]+b[j]<=R){
                add(i,j,w[i]);
            }
        }
    }
	dis[1]=0;
	q.push(make_pair(0,1));
	while(q.size()){
		int kk=q.top().second;
		q.pop();
		if(g[kk]==1){
			continue;
		}
		g[kk]=1;
		for(int j=h[kk];j;j=nxt[j]){
			if(!g[to[j]]){
				if(dis[kk]+val[j]<dis[to[j]]){
					dis[to[j]]=dis[kk]+val[j];
					q.push(make_pair(dis[to[j]],to[j]));
				}
			}
			
		}
	}
	for(int i=1;i<=n;i++){
		if(dis[i]==1e15){
			cout<<-1<<" ";
		}
		else{
			cout<<dis[i]+w[i]<<" ";
		}
		 
	} 
}