比赛 期末考试1 评测结果 AWWWWAWTWT
题目名称 Communication 最终得分 20
用户昵称 2_16鸡扒拌面 运行时间 4.299 s
代码语言 C++ 内存使用 20.79 MiB
提交时间 2026-02-08 10:35:03
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int MAXN=500005;
const LL INF=1LL<<60;

struct Person 
{
    int id;
    int a, b, w;
} p[MAXN];
int N,L,R;
LL dist[MAXN];
struct Node 
{
    int b,id;
    Node(int b=0,int id=0):b(b),id(id){}
    bool operator<(const Node &rhs) const
    {
        if (b!=rhs.b) return b<rhs.b;
        return id<rhs.id;
    }
};
set<Node> s;
vector<int> te;

int main() {
    freopen("tioj_communication.in","r",stdin);
    freopen("tioj_communication.out","w",stdout);
    cin>>N>>L>>R;
    for (int i=1;i<=N;++i) 
    {
        cin>>p[i].a;
        p[i].id = i;
    }
    for(int i=1;i<=N;++i) cin>>p[i].b;
    for(int i=1;i<=N;++i) cin>>p[i].w;
    for(int i=1;i<=N;++i) dist[i] = INF;
    dist[1]=p[1].w;
    for(int i=1;i<=N;++i) if(i!=1) s.insert(Node(p[i].b,i));
    priority_queue<pair<LL, int>, vector<pair<LL, int> >, greater<pair<LL, int> > > pq;
    pq.push(make_pair(dist[1],1));
    while(!pq.empty()) 
    {
        LL d=pq.top().first;
        int u=pq.top().second;
        pq.pop();
        if (d>dist[u]) continue;
        int low=L-p[u].a;
        int high=R-p[u].a;
        //下面这段不会拼,只能复制现成的了
        set<Node>::iterator it_low = s.lower_bound(Node(low, 0));
        set<Node>::iterator it_high = s.upper_bound(Node(high, N+1));
        te.clear();
        for(set<Node>::iterator it=it_low;it!=it_high;++it) 
        {
            int v=it->id;
            if (dist[v]>d+p[v].w) 
            {
                dist[v]=d+p[v].w;
                pq.push(make_pair(dist[v],v));
                te.push_back(v);
            }
        }
        for(int i=0;i<te.size();++i) 
        {
            int v=te[i];
            s.erase(Node(p[v].b,v));
        }
    }
    for (int i=1;i<=N;++i) 
    {
        if (dist[i]>=INF) cout<<-1;
        else cout<<dist[i]<<" ";
    }
    return 0;
}