好题。
今天模拟赛出到这题的究极强化版，于是来写一下这题，也就是弱化版（你管这叫弱化版）
其实思路不难，但是比较有趣。
首先我们肯定是要维护这么一个高精的，但是如果直接维护肯定鉴定为寄。
考虑其他维护方法。
首先要知道 \(dij\) 是肯定不能少的。
我们思考 \(dij\) 主要有两个操作。
-
加法
-
比大小
也就是说如果我们可以在时间复杂度允许范围内做出这些操作，这题就做完了。
加法
考虑到所有边的权值都是 \(2^x\) 的特殊性。
我们考虑将他变成二进制进行维护。
而我们每走一条边就要在一位上加 \(1\)
这就导致了要进行进位。
而如果要进位我们需要将连续一段 \(1\) 变成 \(0\) ，再将一个 \(0\) 变成 \(1\)
考虑到这是区间推平和单点修改，我们可以使用线段树维护，但是由于对每个点都要维护，所以我们考虑使用主席树。
对于区间推平，我们先建出一个全部节点权值为 \(0\) 的主席树，然后将对应区间上的节点接到我们所需区间即可。
对于单点修改没什么好说的。
我们加法一共要执行 \(m\) 次，也就是说加法的总时间复杂度是 \(m\log n\)
比大小
直接比，肯定不行。
考虑哈希，找到第一个不同的位置，然后比较两数大小即可，直接线段树二分即可。
我们使用优先队列要耗费 \(q\log n\) 的时间复杂度，加上线段树二分，就是 \(q\log n\log |V|\) 的时间复杂度。
总时间复杂度 \(m\log n+q\log n\log |V|\)
空间复杂度 \(m\log |V|\)
点击查看代码
#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
const int MAXN=1e5+100,N=1e5+20,MODD=1e9+7,NN=MAXN*77;
int n,m,S,T,tot;
int pw[N];
struct daduoli {
int f,t,w;
}que[MAXN*2];
int cnt,h[MAXN];
void add(int f,int t,int w) {
que[++cnt].f=h[f];
que[cnt].t=t;
que[cnt].w=w;
h[f]=cnt;
}
int rt[MAXN],sf[MAXN],pre[MAXN];
struct trr {
int lc[NN],rc[NN],sum[NN],sz[NN];
LL hs[NN];
void zt(int x,int v) {
lc[x]=lc[v]; sum[x]=sum[v];
rc[x]=rc[v]; sz[x]=sz[v]; hs[x]=hs[v];
}
void psup(int x) {
sum[x]=sum[lc[x]]+sum[rc[x]];
hs[x]=((LL)pw[sz[lc[x]]]*hs[rc[x]]%MODD+hs[lc[x]])%MODD;
}
void build(int &x,int l,int r) {
x=++tot;
sz[x]=r-l+1; hs[x]=0;
if(l==r) return ;
int mid=(l+r)/2;
build(lc[x],l,mid);
build(rc[x],mid+1,r);
psup(x);
}
void insert(int &x,int u,int l,int r,int w) {
x=++tot; zt(x,u);
if(l==r) {
++hs[x];
++sum[x];
return ;
}
int mid=(l+r)/2;
if(w<=mid) insert(lc[x],lc[u],l,mid,w);
if(w>mid) insert(rc[x],rc[u],mid+1,r,w);
psup(x);
}
void update(int &x,int u,int ori,int l,int r,int L,int R) {
if(l>=L&&r<=R) {
x=ori;
return ;
}
x=++tot; zt(x,u);
int mid=(l+r)/2;
if(L<=mid) update(lc[x],lc[u],lc[ori],l,mid,L,R);
if(R>mid) update(rc[x],rc[u],rc[ori],mid+1,r,L,R);
psup(x);
}
int query(int x,int l,int r,int L,int R) {
if(l>R||r<L) return 0;
if(l>=L&&r<=R) return sum[x];
int mid=(l+r)/2;
return (query(lc[x],l,mid,L,R)+query(rc[x],mid+1,r,L,R));
}
int QUERY(int x,int l,int r,int p,int num) {
if(l==r) return l;
int mid=(l+r)/2;
if(sum[lc[x]]>=mid-p+1+num) return QUERY(rc[x],mid+1,r,p,num-sum[lc[x]]);
return QUERY(lc[x],l,mid,p,num);
}
void mdf(int &x,int lst,int w) {
int c=(w>0?query(lst,0,N,0,w-1):0);
int y=QUERY(lst,0,N,w,c);
if(y>w) update(x,lst,rt[0],0,N,w,y-1);
else x=lst;
insert(x,x,0,N,y);
}
bool cmp(int a,int b,int l,int r) {
if(l==r) return sum[a]>sum[b];
int mid=(l+r)/2;
if(hs[rc[a]]==hs[rc[b]]) return cmp(lc[a],lc[b],l,mid);
return cmp(rc[a],rc[b],mid+1,r);
}
} T1;
void init() {
pw[0]=1;
for(int i=1;i<=N-1;++i) pw[i]=pw[i-1]*2%MODD;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i) {
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
add(v,u,w);
}
}
struct ddl {
int id,rt;
bool operator <(const ddl &a)const {
return T1.cmp(rt,a.rt,0,N);
}
};
priority_queue<ddl> q;
void dij() {
T1.build(rt[0],0,N); rt[S]=rt[0]; q.push({S,rt[S]});
while(!q.empty()) {
int u=q.top().id; q.pop();
if(sf[u]) continue; sf[u]=1;
if(u==T) break;
for(int i=h[u];i;i=que[i].f) {
int t=que[i].t;
T1.mdf(rt[n+1],rt[u],que[i].w);
if(!rt[t]||T1.cmp(rt[t],rt[n+1],0,N)) {
rt[t]=rt[n+1];
pre[t]=u;
q.push({t,rt[t]});
}
}
}
if(!sf[T]) {
puts("-1");
exit(0);
}
else printf("%lld\n",T1.hs[rt[T]]);
int x=T,cnt=0;
vector<int> e;
while(x) {
++cnt;
e.push_back(x);
x=pre[x];
}
printf("%d\n",cnt);
for(int len=e.size()-1,i=len;i>=0;--i) {
printf("%d ",e[i]);
}
}
int main () {
init();
scanf("%d%d",&S,&T);
dij();
return 0;
}
/*
4 3
1 2 0
2 3 0
3 4 0
1 4
*/