Codeforces Round #265(Div.1)E The Classic Problem

問題文

http://codeforces.com/contest/464/problem/E

問題概要

頂点数 n 辺数 m の無向グラフが与えられるので, 頂点 s から 頂点 t までの最短経路を求めよ. 存在しない場合は-1, 複数ある場合はどれでもよい.
ただし辺のコストは, 辺ごとに x_i が与えられて 2^x_i で表される.

制約：1 ≤ n ≤ 10^5, 0 ≤ m ≤ 10^5, 0 ≤ x_i ≤ 10^5

解法

当然, ダイクストラをします.
でもコストがヤバすぎるので, 距離をうまく管理する方法を考えようという問題ですね.
ダイクストラをするために必要な, 距離に対する操作を整理するとこんな感じになると思います.

• 距離 a にコスト 2^x_i を足した距離を作成
• 距離 a と距離 b の比較

足し算は O(m) 回, 比較は O(mlogn) 回行われます.（もしかしたら実装にも依るかもしれないですが）
なのでそれぞれ O((logX)^2), O(logX) (X は x_i の最大値) かそれより速いくらいでできれば間に合いそうです.

これができればあとは, 経路復元をするだけですね.

足し算

まず, 足し算について考えましょう.
二進数での各桁をセグメントツリーで管理することにします.
とりあえず, 距離を新しく作成することは置いておいて, 破壊的操作で足し算を行うものとします.
繰り上がりなどを考えると, 以下の操作が必要になります.

• ある桁より上の桁で一番最初の 0 の位置を見つける
• ある区間をすべて 0 にする
• ある桁の値を 1 にする

一つ目の操作は少し厄介ですが, ある区間の 1 の個数を求めることができれば, 位置で二分探索を行って O((logX)^2) でできます.
二つ目の操作は, 各ノードでフラグを持たせて, もしフラグが立っていれば全て 0 で埋めるように子ノードに伝搬していくという, 遅延評価を行えば O(logX) でできます.
三つ目の操作は, 普通のセグメントツリーの一点更新をすれば O(logX) でできます

これで, 破壊的に足し算することはできるようになりましたが, さらにこのセグメントツリーを永続化することで, 変更前と変更後を両方得ることができるので, 本来の "距離 a にコスト 2^x_i を足した距離を作成" の操作が可能になります.

さて, ひとまず足し算が可能になりましたが, 永続セグメントツリーでさらに遅延伝搬をするのはできればやりたくありません.
というわけで, 二つ目の操作における, あるノードに対してそのノード以下のノード全てを 0 で埋めるという操作を, フラグを持たせて管理するのではなく, 単純にヌルポインタで置き換える, というだけで実現しましょう. （詳しくはソースコードを見てください）

比較

次に, 距離同士の比較について考えましょう.
二つの二進数の値の比較をするためには, 異なる最も上の桁を見つける必要があります.
それをセグメントツリーで行うなら, 二つのノードに対して, 互いの部分木の中に異なるものが存在するかどうかが簡単にわかればできそうです.
各ノードに対してその部分木の状態をハッシュ値で持たせてやれば, 等しければすべて一致, 等しくなければ一致しない桁が存在する, という風にわかります.

やり方はいろいろありそうですが, 自分の場合は Zobrist Hash でやりました.
各桁に乱数を付けておいて, 各部分木のハッシュ値を, ビットが立っているの全桁の乱数の排他的論理和にするという方法です.
ハッシュ値同士の比較回数がO(m * logn * logX) くらいありそうなので, 64bitサイズの乱数を使いましょう.
（32bitではたぶん衝突します）

これであとは, 部分木の状態が等しいか等しくないかがO(1)でわかるので, 二つの永続セグメントツリーを根ノードから下りていって, 異なる一番上の桁（無いなら根ノードで分かる）を見つけて比較すると, 距離同士の比較がO(logX) で可能になります.

ソースコード

http://codeforces.com/contest/464/submission/35545845

#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;

const int mod = 1e9 + 7;

int pow2(int x) {
	long long res = 1, t = 2;
	while (x) {
		if (x & 1) {
			res = (res * t) % mod;
		}
		t = (t * t) % mod;
		x >>= 1;
	}
	return (int)res;
}

const int MAX = 1 << 17;

ull hs[MAX];

void init() {
	random_device rd;
	mt19937_64 mt(rd());
	for (int i = 0; i < MAX; i++) {
		hs[i] = mt();
	}
}

struct edge {
	int from, to, cost;
	edge() : cost(-1) {}
	edge(int f, int t, int c) : from(f), to(t), cost(c) {}
};
using edges = vector<edge>;
using graph = vector<edges>;

struct node {
	int cnt;
	ull ha;
	node *lch, *rch;
	node() : cnt(0), ha(0), lch(nullptr), rch(nullptr) {}
};

node* fix(node *x) {
	node *y = new node();
	if (x) *y = *x;
	return y;
}

node* update(node *x) {
	if (!x) return x;
	x->cnt = (x->lch ? x->lch->cnt : 0) + (x->rch ? x->rch->cnt : 0);
	x->ha = (x->lch ? x->lch->ha : 0) ^ (x->rch ? x->rch->ha : 0);
	return x;
}

int count_one(node *x, int l, int r, int lb = 0, int ub = MAX) {
	if (!x || r <= lb || ub <= l) return 0;
	if (l <= lb && ub <= r) return x->cnt;
	int c = (lb + ub) / 2;
	return count_one(x->lch, l, r, lb, c) + count_one(x->rch, l, r, c, ub);
}

node* fill_zero(node *x, int l, int r, int lb = 0, int ub = MAX) {
	if (!x || r <= lb || ub <= l) return x;
	if (l <= lb && ub <= r) return nullptr;
	x = fix(x);
	int c = (lb + ub) / 2;
	x->lch = fill_zero(x->lch, l, r, lb, c);
	x->rch = fill_zero(x->rch, l, r, c, ub);
	return update(x);
}

node* add_one(node *x, int p, int lb = 0, int ub = MAX) {
	x = fix(x);
	if (ub - lb == 1) {
		x->cnt = 1;
		x->ha = hs[p];
		return x;
	}
	int c = (lb + ub) / 2;
	if (p < c) {
		x->lch = add_one(x->lch, p, lb, c);
	}
	else {
		x->rch = add_one(x->rch, p, c, ub);
	}
	return update(x);
}

node* add(node *rt, int x) {
	int lb = x, ub = MAX;
	while (ub - lb > 1) {
		int m = (lb + ub) / 2;
		if (count_one(rt, x, m) == m - x) {
			lb = m;
		}
		else {
			ub = m;
		}
	}
	rt = fill_zero(rt, x, lb);
	rt = add_one(rt, lb);
	return rt;
}

bool is_greater(node* l, node* r) {
	if (!l) return false;
	if (!r) return true;
	if (l->ha == r->ha) return false;
	for (int i = 0; l && r && i < 17; i++) {
		if ((l->rch ? l->rch->ha : 0) != (r->rch ? r->rch->ha : 0)) {
			l = l->rch;
			r = r->rch;
		}
		else {
			l = l->lch;
			r = r->lch;
		}
	}
	return l && l->ha;
}

struct dijk_node {
	node *dis;
	edge ed;
	dijk_node(node *d, const edge& e) : dis(d), ed(e) {}
};

bool operator>(const dijk_node& l, const dijk_node& r) {
	return is_greater(l.dis, r.dis);
}

edges dijkstra(int s, const graph& G) {
	priority_queue<dijk_node, vector<dijk_node>, greater<dijk_node>> pq;
	vector<bool> kaku(G.size());
	edges tree(G.size());
	pq.emplace(nullptr, edge(-1, s, -1));
	while (!pq.empty()) {
		auto p = pq.top(); pq.pop();
		int v = p.ed.to;
		if (kaku[v]) continue;
		kaku[v] = true;
		if (v != s) tree[v] = edge(v, p.ed.from, p.ed.cost);
		for (auto e : G[v]) if (!kaku[e.to]) {
			pq.emplace(add(p.dis, e.cost), e);
		}
	}
	return tree;
}

int main()
{
	ios::sync_with_stdio(false), cin.tie(0);
	init();
	int n, m;
	cin >> n >> m;
	graph G(n);
	for (int i = 0; i < m; i++) {
		int u, v, x;
		cin >> u >> v >> x; u--, v--;
		G[u].emplace_back(u, v, x);
		G[v].emplace_back(v, u, x);
	}
	int s, t;
	cin >> s >> t; s--, t--;
	auto tree = dijkstra(s, G);
	int dist = 0;
	vector<int> res;
	while (t != s) {
		if (tree[t].cost == -1) {
			cout << -1 << endl;
			return 0;
		}
		res.push_back(t);
		dist = (dist + pow2(tree[t].cost)) % mod;
		t = tree[t].to;
	}
	cout << dist << endl;
	res.push_back(t);
	reverse(res.begin(), res.end());
	cout << res.size() << endl;
	for (int i = 0; i < (int)res.size(); i++) {
		cout << res[i] + 1 << " \n"[i + 1 == (int)res.size()];
	}
	return 0;
}