补一补之前听课时候的题.
考虑使用 dij 算法求最短路, 因为边权存不下, 所以考虑用主席树维护二进制位, 因为每一次都只会在一个位置进行修改, 所以可以暴力进位, 这样均摊复杂度是对的.
算法导论给了证明: 对于一个有 $k$ 位的二进制计数器, 假设每一次都从第 0 位 $+1$, 那么我们发现执行 $n$ 次加法之后, 发现第零位会变 $\left \lfloor \frac{n}{1} \right \rfloor$ 次, 第一位会变 $\left \lfloor \frac{n}{2} \right \rfloor$ 次... 而第 $n$ 位会变 $\left \lfloor \frac{n}{2^n} \right \rfloor$ 次, 这样子所有的操作次数就相当于 $\sum_{i = 0}^{k - 1}\left \lfloor \frac{i}{2^i} \right \rfloor <n * \sum_{i = 0}^{\infty}\frac{1}{2^i} = 2n$, 所以最坏情况下的时间为 $O(n)$, 每一次操作的均摊时间复杂度为 $O(n) / n = O(1)$.
这样子只需要借助主席树写一个时间为 $O(log)$ 的 $cmp$ 函数就可以用堆优化 dijkskra 了, 遇到进位就在线段树上暴力搞一搞, 反正复杂度是对的.
数太大了直接用题目中给的 $seed = 2, Mod = 1e9 + 7$ 的哈希哈希一下就好了.
时间复杂度 $O(nlog^2n)$.
感觉就像是对着大佬的题解抄了一遍.
Code:
- #include <cstdio>
- #include <cstring>
- #include <queue>
- #include <cstdlib>
- using namespace std;
- const int N = 1e5 + 5;
- const int P = 1e9 + 7;
- int n, m, st, ed, lim = 0, bin[N <<1];
- int tot = 0, head[N], pre[N];
- struct Edge {
- int to, nxt, val;
- } e[N << 1];
- inline void add(int from, int to, int val) {
- e[++tot].to = to;
- e[tot].val = val;
- e[tot].nxt = head[from];
- head[from] = tot;
- }
- inline void read(int &X) {
- X = 0; char ch = 0; int op = 1;
- for(; ch> '9'|| ch <'0'; ch = getchar())
- if(ch == '-') op = -1;
- for(; ch>= '0' && ch <= '9'; ch = getchar())
- X = (X <<3) + (X << 1) + ch - 48;
- X *= op;
- }
- inline void chkMax(int &x, int y) {
- if(y> x) x = y;
- }
- namespace PSegT {
- struct SegNode {
- int lc, rc, w;
- } s[N * 120];
- int nodeCnt, root[N];
- #define mid ((l + r)>> 1)
- bool cmp(int x, int l, int r, int y) {
- if(l == r) return s[x].w> s[y].w;
- if(s[s[x].rc].w == s[s[y].rc].w) return cmp(s[x].lc, l, mid, s[y].lc);
- else return cmp(s[x].rc, mid + 1, r, s[y].rc);
- }
- bool modify(int &x, int l, int r, int pos, int y) {
- s[x = ++nodeCnt] = s[y];
- if(l == r) {
- s[x].w = s[y].w ^ 1;
- return s[y].w;
- }
- int res;
- if(pos> mid) res = modify(s[x].rc, mid + 1, r, pos, s[y].rc);
- else {
- res = modify(s[x].lc, l, mid, pos, s[y].lc);
- if(res) res = modify(s[x].rc, mid + 1, r, mid + 1, s[y].rc);
- }
- s[x].w = (1LL * s[s[x].rc].w * bin[mid - l + 1] % P + s[s[x].lc].w) % P;
- return res;
- }
- } using namespace PSegT;
- struct Node {
- int x, rt;
- bool operator <(const Node &oth) const {
- return cmp(rt, 0, lim, oth.rt);
- }
- };
- priority_queue <Node> Q;
- void dfs(int x, int dep) {
- if(x == st) {
- printf("%d\n%d", dep, x);
- return;
- }
- dfs(pre[x], dep + 1);
- printf("%d", x);
- }
- inline void out() {
- printf("%d\n", s[root[ed]].w);
- dfs(ed, 1);
- printf("\n");
- exit(0);
- }
- int main() {
- read(n), read(m);
- for(int x, y, v, i = 1; i <= m; i++) {
- read(x), read(y), read(v);
- add(x, y, v), add(y, x, v);
- chkMax(lim, v);
- }
- lim += 100;
- read(st), read(ed);
- for(int i = bin[0] = 1; i <= lim; i++)
- bin[i] = 1LL * bin[i - 1] * 2 % P;
- nodeCnt = 0;
- Q.push((Node) {st, root[st]});
- for(; !Q.empty(); ) {
- Node now = Q.top(); Q.pop();
- if(now.rt != root[now.x]) continue;
- if(now.x == ed) out();
- for(int i = head[now.x]; i; i = e[i].nxt) {
- int y = e[i].to, v;
- modify(v, 0, lim, e[i].val, root[now.x]);
- if(!root[y] || cmp(root[y], 0, lim, v)) {
- root[y] = v;
- Q.push((Node) {y, root[y]});
- pre[y] = now.x;
- }
- }
- }
- puts("-1");
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2749503.html