| 比赛 |
期末考试1 |
评测结果 |
AWWWTTTTTT |
| 题目名称 |
Communication |
最终得分 |
10 |
| 用户昵称 |
汐汐很希希 |
运行时间 |
6.773 s |
| 代码语言 |
C++ |
内存使用 |
193.33 MiB |
| 提交时间 |
2026-02-08 11:01:15 |
显示代码纯文本
#include<bits/stdc++.h>
#define ll long long
const int N=5e5+10;
const int M=1e5+10;
const int MOD=1e9+7;
const int MAXX=2e9;
using namespace std;
int n,l,r,d[N],vis[N];
struct node{
int a,b,w;
}s[N];
vector<int> g[N];
vector<int> e[N];
void add(int u,int v,int w){
g[u].push_back(v);
e[u].push_back(w);
return;
}
struct Node{
int dis,u;
bool operator>(const Node& a) const { return dis>a.dis; }
};
priority_queue<Node, vector<Node>, greater<Node> > q;
void dijkstra(int s)
{
memset(d,0x3f,sizeof(d));
memset(vis,0,sizeof(vis));
d[s]=0;
q.push({0,s});
while(!q.empty()){
int u=q.top().u;
q.pop();
if(vis[u]) continue;
vis[u]=1;
for(int i=0;i<g[u].size();i++){
int v=g[u][i],w=e[u][i];
if(d[v]>d[u]+w){
d[v]=d[u]+w;
q.push({d[v],v});
}
}
}
return;
}
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>>s[i].a;
for(int i=1;i<=n;i++) cin>>s[i].b;
for(int i=1;i<=n;i++) cin>>s[i].w;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j) continue;
if(l<=s[i].a+s[j].b&&s[i].a+s[j].b<=r){
add(i,j,s[i].w);
}
}
}
dijkstra(1);
cout<<s[1].w<<' ';
for(int i=2;i<=n;i++) cout<<d[i]+s[i].w<<' ';
return 0;
}