CF464E 解题报告

首先这是一道最短路的题目，但是数据范围十分庞大，需要高精度。但是数据范围实在太庞大了，高精度的时间复杂度是很高的，所以我们另辟蹊径。

考虑到每条边边权都是 \(2^x\) 的形式，提示我们将起点到每个点的最短距离转化为二进制形式。考虑松弛操作需要用到什么，发现需要比较两个二进制数的大小，以及两个二进制数的相加。

对于比大小，我们只需要用 hash 找到两个二进制数的最长公共前缀，比较最长公共前缀的下一位就行。

对于相加，我们发现其中一个加数是 \(2^x\) 的形式，意味着会有一段连续的 \(1\) 变成 \(0\)，再将一个 \(0\) 变成 \(1\)（自己手动模拟一下会发现）。这个操作只需要先二分出端点，再用线段树操作即可。

？？线段树？有 \(n\) 个点，每个点如果都维护一个最长为 \(10^5\) 位的二进制数，显然是存不下的。所以我们用可持久化线段树来维护，以 \(root_i\) 为根的线段树代表起点到 \(i\) 的最短距离的二进制形式。主席树内需要维护当前区间 hash 值，和最短距离 sum。

1.64s / 395.52MB / 3.61KB / C++14 (GCC 9)

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5, mod = 1e9 + 7;

int n, m, S, T, pw2[N], b[N], root[N], idx;
vector<pair<int, int> > G[N];

struct edge {
	int l, r;
	int sum, flg, has;
}tr[N * 100];

void push_up(int p) {
	tr[p].sum = (tr[tr[p].l].sum + tr[tr[p].r].sum) % mod; // sum为最短距离
	tr[p].flg = tr[tr[p].l].flg & tr[tr[p].r].flg; // flg表示这个区间是否全部为1，用于来找连续的1
	tr[p].has = (tr[tr[p].l].has % mod + tr[tr[p].r].has) % mod; // hash
}

int build(int l, int r, int v) {
	int p = ++idx;
	if (l == r) {
		tr[p].sum = pw2[l] * v % mod;
		tr[p].flg = v, tr[p].has = b[l] * v % mod;
		return p;
	}
	int mid = (l + r) >> 1;
	tr[p].l = build(l, mid, v);
	tr[p].r = build(mid + 1, r, v);
	push_up(p);
	return p;
}

int query_flg(int p, int l, int r, int L, int R) { // [L,R] 区间是否全部为1
	if (L <= l && r <= R) return tr[p].flg;
	int res = 1, mid = (l + r) >> 1;
	if (L <= mid) res &= query_flg(tr[p].l, l, mid, L, R);
	if (R > mid) res &= query_flg(tr[p].r, mid + 1, r, L, R);
	return res;
}

int clear(int now, int l, int r, int L, int R) { // 将 [L,R] 置 0
	int p = ++idx;
	tr[p] = tr[now];
	if (L <= l && r <= R) {
		tr[p] = {0, 0, 0, 0, 0}; // 我们可以直接将子树都丢掉，不用标记永久花
		return 0;
	}
	int mid = (l + r) >> 1;
	if (L <= mid) tr[p].l = clear(tr[now].l, l, mid, L, R);
	if (R > mid) tr[p].r = clear(tr[now].r, mid + 1, r, L, R);
	push_up(p);
	return p;
}

int modify(int now, int l, int r, int x) { // x 位变为1
	int p = ++idx;
	tr[p] = tr[now];
	if (l == r) {
		tr[p].sum = pw2[l];
		tr[p].has = b[l], tr[p].flg = 1;
		return p;
	}
	int mid = (l + r) >> 1;
	if (x <= mid) tr[p].l = modify(tr[now].l, l, mid, x);
	else tr[p].r = modify(tr[now].r, mid + 1, r, x);
	push_up(p);
	return p;
}

void addone(int rt, int x) { // 加上2^x的结果，存到root[n+1]的线段树内
	int l = x, r = N - 5;
	while (l < r) {
		int mid = (l + r + 1) >> 1;
		if (query_flg(root[rt], 0, N - 5, x, mid)) l = mid;
		else r = mid - 1;
	}
	root[n + 1] = root[rt];
	if (x <= l && query_flg(root[rt], 0, N - 5, x, l)) {
		root[n + 1] = clear(root[n + 1], 0, N - 5, x, l);
		root[n + 1] = modify(root[n + 1], 0, N - 5, l + 1);	
	}
	else {
		root[n + 1] = modify(root[n + 1], 0, N - 5, l);	
	}
//	cout << "ww=" << query_flg(root[n + 1], 0, N - 5, x - 1, x) << endl;
}

int cmp(int a, int b, int l, int r) { // 比较大小
	if (l == r) return tr[a].flg > tr[b].flg;
	int mid = (l + r) >> 1;
	if (tr[tr[a].r].has != tr[tr[b].r].has) return cmp(tr[a].r, tr[b].r, mid + 1, r);
	return cmp(tr[a].l, tr[b].l, l, mid);
}

struct node {
	int u, rt;
	friend bool operator < (node a, node b) {
		return cmp(a.rt, b.rt, 0, N - 5);
	}
};
priority_queue<node> q;
int st[N], pre[N];

void dij() {
	root[S] = build(0, N - 5, 0);
	root[0] = build(0, N - 5, 1);
	for (int i = 1; i <= n; i++) {
		if (i != S) root[i] = root[0];
	}
	q.push({S, root[S]});
	while (q.size()) {
		auto t = q.top(); q.pop();
		int u = t.u;
		if (st[u]) continue;
		st[u] = 1;
		for (auto e : G[u]) {
			int v = e.first, w = e.second;
			addone(u, w);
			if (cmp(root[v], root[n + 1], 0, N - 5)) {
				root[v] = root[n + 1];
				pre[v] = u;
				q.push({v, root[v]});
			}
		}
	}
}

vector<int> ans;

signed main() {
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		G[u].push_back({v, w});
		G[v].push_back({u, w});
	}
	pw2[0] = b[0] = 1;
	for (int i = 1; i <= N - 4; i++) pw2[i] = pw2[i - 1] * 2 % mod, b[i] = b[i - 1] * 131 % mod;
	cin >> S >> T;
	dij();
	if (tr[root[T]].sum == pw2[N - 4] - 1) puts("-1"), exit(0);
	cout << tr[root[T]].sum << endl;
	int tmp = T;
	while (tmp != S) {
		ans.push_back(tmp);
		tmp = pre[tmp];
	}
	ans.push_back(S);
	cout << ans.size() << endl;
	reverse(ans.begin(), ans.end());
	for (auto v : ans) cout << v << ' ';
}