AC 22 WA 22 玄关 求条

AT 提交记录

#include <bits/stdc++.h>
using namespace std;
#define int long long 
const int inf = (1ll << 60);
const int N = 3e5 + 5, M = 3e5 + 5;
int n, m, k, d, a[N], b[N], hd[N], idx = 0, vis[N];
int seg[N << 2];
int lc(int x) {return x << 1;}
int rc(int x) {return x << 1 | 1;}
struct edge {
	int to, val, nxt;
} e[M << 1];
struct info {
	int t, d;
	friend bool operator < (info u, info v) {
		return (u.t == v.t ? u.d < v.d : u.t < v.t);
	}
} dis[N];
struct node {
	int id; info val;
	friend bool operator < (node u, node v) {
		return (u.val.t == v.val.t ? u.val.d < v.val.d : u.val.t < v.val.t);
	}
};
priority_queue <node> q;
void add_edge(int u, int v, int w) {
	e[++idx].to = v, e[idx].val = w, e[idx].nxt = hd[u];
	hd[u] = idx;
}
void init_dij() {
	memset(dis, 0x3f, sizeof dis);
	for (int i = 1; i <= k; i++) {
		q.push((node){a[i], (info){0, 0}});
		dis[a[i]] = (info){0, 0};
	}
}
void push_up(int rt) {
	seg[rt] = max(seg[lc(rt)], seg[rc(rt)]);
}
void build(int rt, int l, int r) {
	if (l == r) {
		seg[rt] = b[l];
		return ;
	}
	int mid = (l + r) >> 1;
	build(lc(rt), l, mid); build(rc(rt), mid + 1, r);
	push_up(rt);
}
int query(int L, int R, int rt, int l, int r) {
	if (l >= L && r <= R) return seg[rt];
	int mid = (l + r) >> 1, res = 0;
	if (L <= mid) res = max(res, query(L, R, lc(rt), l, mid));
	if (R > mid) res = max(res, query(L, R, rc(rt), mid + 1, r));
	return res;
}
void dijkstra() {
	while (!q.empty()) {
		int u = q.top().id;
		dis[u].t = q.top().val.t, dis[u].d = q.top().val.d;
		q.pop();
//		cout << dis[u].t << ' ' << dis[u].d << '\n';
		if (vis[u]) continue ;
		vis[u] = 1;
		for (int i = hd[u]; i; i = e[i].nxt) {
			int v = e[i].to, w = e[i].val;
			info tmp = (info){dis[u].t, dis[u].d + w}; // v与u同一天被传染
			if (dis[u].d + w <= b[dis[u].t] && tmp < dis[v]) {
				dis[v] = tmp;
				q.push((node){v, dis[v]});
				continue ;
			}
			if (dis[u].t >= d) continue ;
			int l = dis[u].t + 1, r = d, mid, res = 0;
			if (query(l, r, 1, 1, d) < w) { // 最大值都小于 w
				res = r + 1;
			} else {
				while (l <= r) {
					mid = (l + r) >> 1;
					if (query(dis[u].t + 1, mid, 1, 1, d) >= w) r = mid - 1, res = mid;
					else l = mid + 1;
				}
			}
//			cout << res << "\n\n";
			if (res > d) continue ;
			tmp = (info){res, w}; // v与u不同一天被传染
			if (tmp < dis[v]) {
				dis[v] = tmp;
				q.push((node){v, dis[v]});
				continue ;
			}
		}
	}
}
signed main() {
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int u, v, w; cin >> u >> v >> w;
		add_edge(u, v, w); add_edge(v, u, w);
	}
	cin >> k;
	for (int i = 1; i <= k; i++) cin >> a[i];
	cin >> d;
	for (int i = 1; i <= d; i++) cin >> b[i];
	build(1, 1, d);
	init_dij();
	dijkstra();
	for (int i = 1; i <= n; i++)
		cout << (dis[i].t <= d ? dis[i].t : -1) << '\n';
	return 0; 
}