比赛 期末考试1 评测结果 WAAATTTTTT
题目名称 Communication 最终得分 30
用户昵称 杨蕙宇 运行时间 6.639 s
代码语言 C++ 内存使用 192.31 MiB
提交时间 2026-02-08 11:38:27
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+10;
const ll INF=0x3f3f3f3f;
ll n,a[N],b[N],w[N],l,r,dis[N],mk[N];
vector<ll>e[N];
void dijkstra(int u){
    for(int i=0;i<=n;i++)dis[i]=INF;
    dis[u]=w[u];
    mk[u]=1;
    while(1){
        ll t=-1;
        for(int j=0;j<e[u].size();j++){
            ll v=e[u][j];
            if(!mk[v]&&(t==-1||w[v]+dis[u]<dis[t])){
                t=v;
                dis[t]=dis[u]+w[t];
            }
        }
        if(t==-1||dis[t]==INF)break;
        mk[t]=1;
        for(int j=0;j<e[t].size();j++){
            ll v=e[t][j];
            if(dis[t]+w[v]<dis[v]){
                dis[v]=dis[t]+w[v];
            }
        }
    } 
} 
int main(){
    freopen("tioj_communication.in","r",stdin);
    freopen("tioj_communication.out","w",stdout);
    ios::sync_with_stdio;
    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(a[i]+b[j]>=l&&a[i]+b[j]<=r){
                e[i].push_back(j);
            }
        }
    }
//    for(int i=1;i<=n;i++){
//        for(int j=0;j<v[i].size();j++){
//            cout<<i<<" "<<v[i][j]<<endl; 
//        }
//    }
    dijkstra(1);
    for(int i=1;i<=n;i++){
        if(dis[i]==INF)cout<<-1<<" ";
        else cout<<dis[i]<<" ";
    }
    return 0;
}