比赛 期末考试1 评测结果 AAAATMTTTT
题目名称 Communication 最终得分 40
用户昵称 yyswys 运行时间 6.417 s
代码语言 C++ 内存使用 302.74 MiB
提交时间 2026-02-08 11:35:14
显示代码纯文本
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+5,inf=1e12;
int n,l,r;
int a[N],b[N],w[N];
struct edge{int v,w;};
struct node{
	int di,u;	
	bool operator>(const node&a) const{return di>a.di;}
};
vector<edge>e[N];
int dis[N],vis[N];
priority_queue<node,vector<node>,greater<node>>q;
void dij(){
	for(int i(1);i<=n;++i){
		dis[i]=inf;
	}
	dis[1]=0;
	q.push({0,1});
	while(!q.empty()){
		int u=q.top().u;
		q.pop();
		if(vis[u]) continue;
		vis[u]=1;
		for(auto i:e[u]){
			int v=i.v,wl=i.w;
			if(dis[v]>dis[u]+wl){
				dis[v]=dis[u]+wl;
				q.push({dis[v],v});
			}
		}
	}
	for(int i(1);i<=n;++i){
		dis[i]+=w[1];
	}
	return;
}
signed main(){
	freopen("tioj_communication.in","r",stdin);
	freopen("tioj_communication.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>l>>r;
	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(l-a[i]<=b[j]&&b[j]<=r-a[i]){
				e[i].push_back({j,w[j]});
			}
		}
	}
	dij();
	for(int i(1);i<=n;++i){
		if(dis[i]>=inf){
			cout<<"-1 ";
		}else{
			cout<<dis[i]<<" ";
		}
	}
	return 0;
}