思路
\(2^{100000}\) ?别想了,普通高精度肯定不行
但我们发现,求最短路的过程中,其实是用到了比较大小和加法操作
细想比较大小的过程,当长度相同的数,我们会先略过前面相同的部分,比较第一个不同的数字,时间大部分都耗在了相同部分的枚举上
我们就可以使用二分,找出第一个不同的数字
对于如何判断前缀是否相同,我们可以使用 hash
求 LCP
的方法,在这道题中,我们可以将 hash
的底数设为 \(2\),模数设为 \(1e9+7\),可以方便输出
对于加法操作,我们注意到这是二进制加法,当加入 \(2^w\) 时,先找到 \(w\) 位往后的第一个 \(0\) 的位置(设为 \(p\)),然后将 \(w\) ~ \(p-1\) 赋值为 \(0\),将 \(p\) 改为 \(1\)
有区间赋值,我们就考虑可以用线段树;但每个数都开一棵线段树显然是不够空间的,因此我们考虑用主席树,让能够共用的区间更多
找 \(0\) 操作就是在线段树二分
而 hash
也放在线段树上,合并左右儿子时一起更新;比较大小改为线段树二分即可
有了这些,就可以正常跑 dij
了
代码
#include<iostream>
#include<fstream>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#define LL long long
#define maxn 100040
#define mod 1000000007
#define FOR(i, x, y) for(int i = (x); i <= (y); i++)
#define ROF(i, x, y) for(int i = (x); i >= (y); i--)
#define PFOR(i, x) for(int i = he[x]; i; i = e[i].nxt)
inline int reads()
{
int sign = 1, re = 0; char c = getchar();
while(c < '0' || c > '9'){if(c == '-') sign = -1; c = getchar();}
while('0' <= c && c <= '9'){re = re * 10 + (c - '0'); c = getchar();}
return sign * re;
}
int n, m, S, T;
struct Node
{
int to, nxt, w;
}e[200005]; int he[100005];
inline void Edge_add(int u, int v, int w)
{
static int cnt = 0;
e[++cnt] = (Node){v, he[u], w};
he[u] = cnt;
}
inline int mod_add(int x) {return x >= mod ? x - mod : x;}
int pow2[maxn + 5];
namespace Seg_Tree
{
int ls[4000005], rs[4000005];
int sum[4000005], hash[4000005];
int tcnt, rt[100005];
inline void up(int now)
{
sum[now] = sum[ls[now]] + sum[rs[now]];
hash[now] = mod_add(hash[ls[now]] + hash[rs[now]]);
}
int build(int l, int r, int v)
{
int now = ++tcnt;
if(l == r)
{
sum[now] = v;
hash[now] = pow2[l] * v % mod;
return now;
}
int mid = (l + r) >> 1;
ls[now] = build(l, mid, v);
rs[now] = build(mid + 1, r, v);
up(now);
return now;
}
bool cmp(int now1, int now2, int l, int r)
{
if(l == r) return sum[now1] < sum[now2];
int mid = (l + r) >> 1;
bool chk = sum[rs[now1]] == sum[rs[now2]] && hash[rs[now1]] == hash[rs[now2]];
if(chk) return cmp(ls[now1], ls[now2], l, mid);
return cmp(rs[now1], rs[now2], mid + 1, r);
}
int get_sum(int now, int l, int r, int L, int R)
{
if(L <= l && r <= R) return sum[now];
int mid = (l + r) >> 1, re = 0;
if(L <= mid) re += get_sum(ls[now], l, mid, L, R);
if(mid < R) re += get_sum(rs[now], mid + 1, r, L, R);
return re;
}
int Div(int now, int l, int r, int st)
{
if(l == r) return l;
int mid = (l + r) >> 1;
if(mid < st) return Div(rs[now], mid + 1, r, st);
if(get_sum(ls[now], l, mid, st, mid) == mid - st + 1)
return Div(rs[now], mid + 1, r, mid + 1);
return Div(ls[now], l, mid, st);
}
int modify_one(int pre, int l, int r, int to)
{
int now = ++tcnt;
ls[now] = ls[pre], rs[now] = rs[pre];
if(l == r)
{
sum[now] = 1, hash[now] = pow2[l];
return now;
}
int mid = (l + r) >> 1;
if(to <= mid) ls[now] = modify_one(ls[pre], l, mid, to);
else rs[now] = modify_one(rs[pre], mid + 1, r, to);
up(now);
return now;
}
int modify_zero(int now, int zero, int l, int r, int L, int R)
{
if(L <= l && r <= R) return zero;
int nnow = ++tcnt; ls[nnow] = ls[now], rs[nnow] = rs[now];
int mid = (l + r) >> 1;
if(L <= mid) ls[nnow] = modify_zero(ls[now], ls[zero], l, mid,L, R);
if(mid < R) rs[nnow] = modify_zero(rs[now], rs[zero], mid + 1, r, L, R);
up(nnow);
return nnow;
}
int add(int _rt, int w)
{
int pos = Div(_rt, 0, maxn, w);
int rp = modify_one(_rt, 0, maxn, pos);
if(pos == w) return rp;
rp = modify_zero(rp, rt[0], 0, maxn, w, pos - 1);
return rp;
}
} using namespace Seg_Tree;
std::bitset<100005> vis;
struct Dis
{
int u, rt;
};
bool operator > (const Dis a, const Dis b) {return cmp(b.rt, a.rt, 0, maxn);}
std::priority_queue<Dis, std::vector<Dis>, std::greater<Dis>> q;
int pre[100005], ans[100005], acnt;
inline void Dij()
{
int rp = build(0, maxn, 1);
FOR(i, 1, n) rt[i] = rp;
rt[0] = rt[S] = build(0, maxn, 0);
q.push((Dis){S, rt[S]});
while(!q.empty())
{
while(!q.empty() && vis[q.top().u])
q.pop();
if(q.empty()) break;
int now = q.top().u; q.pop();
vis[now] = 1;
PFOR(i, now)
{
int to = e[i].to;
if(vis[to]) continue;
int rp = add(rt[now], e[i].w);
if(cmp(rp, rt[to], 0, maxn))
{
rt[to] = rp, pre[to] = now;
q.push((Dis){to, rt[to]});
}
}
}
if(rt[T] == rp) {puts("-1"); return;}
printf("%d\n", hash[rt[T]]);
int dd = T;
while(dd != S) ans[++acnt] = dd, dd = pre[dd];
ans[++acnt] = S;
printf("%d\n", acnt);
ROF(i, acnt, 1) printf("%d ", ans[i]);
}
signed main()
{
#ifndef ONLINE_JUDGE
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
#endif
n = reads(), m = reads();
FOR(i, 1, m)
{
int u = reads(), v = reads(), w = reads();
Edge_add(u, v, w), Edge_add(v, u, w);
}
S = reads(), T = reads();
pow2[0] = 1;
FOR(i, 1, maxn)
pow2[i] = pow2[i - 1] << 1,
pow2[i] = mod_add(pow2[i]);
Dij();
return 0;
}
标签:rt,Classic,int,CF464E,rs,mid,Problem,now,sum
From: https://www.cnblogs.com/zuytong/p/16647596.html