比赛 期末考试1 评测结果 AWWWEEEEEE
题目名称 Communication 最终得分 10
用户昵称 赵飞羽 运行时间 0.934 s
代码语言 C++ 内存使用 3.68 MiB
提交时间 2026-02-08 11:15:36
显示代码纯文本
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1010, M = 1000010;
int n, l, r, a[N], b[N], w[N], s = 1, dis[N], vis[N];
int hd[N], ver[M], val[M], pre[M], idx;
struct node {
	int u, v;
	bool operator < (const node &x) const {
		return v > x.v;
	}
};
priority_queue <node> q;

void add(int x, int y, int w) {
	ver[++idx] = y;
	val[idx] = w;
	pre[idx] = hd[x];
	hd[x] = idx;
}

void Dijkstra() {
	q.push({s, 0});
	while (!q.empty()) {
		int u = q.top().u;
		q.pop();
		if (vis[u]) continue;
		vis[u] = 1;
		for (int i = hd[u]; i; i = pre[i]) {
			int x = ver[i];
			if (dis[x] > dis[u] + val[i]) {
				dis[x] = dis[u] + val[i];
				q.push({x, dis[x]});
			}
		}
	}
}

signed main() {
    freopen("tioj_communication.in", "r", stdin);
    freopen("tioj_communication.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
	memset(dis, 0x3f, sizeof(dis));
	memset(vis, 0, sizeof(vis));
	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 (i == j) continue;
	        if (a[i] + b[j] >= l && a[i] + b[j] <= r) add(i, j, w[j]);
        }
    }
	dis[s] = 0;
	Dijkstra();
	for (int i = 1; i <= n; i++) cout << dis[i] + w[1] << " ";
    return 0;
}