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