| 比赛 |
期末考试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;
}