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