题目

边权均为2的幂次的无向图，求 \(S\) 到 \(T\) 的最短路

\(n,m\leq 10^5\)

分析

最短路直接考虑用 Dijkstra，它需要维护松弛操作和堆，

那么也就是要重载加号和小于号，而数字可以在主席树上维护。

对于小于号，最直接的一种做法就是从高位到低位找到第一个不同数字的位比较大小，

那么就是先在主席树上二分找到这两个数的LCP，然后比较下一位的大小，

LCP可以用哈希来维护，如果 \(base=2,mod=10^9+7\)，顺便就可以把答案求出来，那么就是一个 \(\log\) 的。

对于加号，找到从第x位起第一个0，然后把左边的1都变成0，只把那个0的位置变成1，

这个维护区间左端点为开头极长的1也可以做到一个 \(\log\)

再加上堆的时间复杂度就是 \(O(m\log n\log mx+m\log mx)\)

代码

#include 
#include 
#include 
using namespace std;
const int mod=1000000007,N=100021; struct node{int y,w,next;}e[N<<1];
int two[N+11],pre[N],n,m,ans,as[N],S,T,rt[N],et=1,st[N],Top,v[N];
int w[N<<6],ls[N<<6],rs[N<<6],len[N<<6],cnt,Cnt; pairheap[N<<1];
int iut(){
	int ans=0; char c=getchar();
	while (!isdigit(c)) c=getchar();
	while (isdigit(c)) ans=ans*10+c-48,c=getchar();
	return ans;
}
void build(int &rt,int l,int r){
	rt=++cnt;
	if (l==r) return;
	int mid=(l+r)>>1;
	build(ls[rt],l,mid);
	build(rs[rt],mid+1,r);
}
bool geq(int fi,int se,int l,int r){
	if (w[fi]==w[se]) return 0;
	if (l==r) return w[fi]>w[se];
	int mid=(l+r)>>1;
	if (w[rs[fi]]==w[rs[se]]) return geq(ls[fi],ls[se],l,mid);
	    else return geq(rs[fi],rs[se],mid+1,r);
}
int zero(int rt,int l,int r,int x,int y){
	if (l==x&&r==y){
		if (len[rt]==r-l+1) return 0x3f3f3f3f;
		    else return l+len[rt];
	}
	int mid=(l+r)>>1;
	if (y<=mid) return zero(ls[rt],l,mid,x,y);
	else if (x>mid) return zero(rs[rt],mid+1,r,x,y);
	else{
		int now=zero(ls[rt],l,mid,x,mid);
		if (now!=0x3f3f3f3f) return now;
		    else return zero(rs[rt],mid+1,r,mid+1,y);
	}
}
void upd(int &rt,int l,int r,int x){
	int trt=++cnt;
	ls[trt]=ls[rt],rs[trt]=rs[rt],rt=trt;
	if (l==r){
		len[rt]=w[rt]=1;
		return;
	}
	int mid=(l+r)>>1;
	if (x<=mid) upd(ls[rt],l,mid,x);
	    else upd(rs[rt],mid+1,r,x);
	w[rt]=(w[ls[rt]]+1ll*w[rs[rt]]*two[mid-l+1]%mod)%mod;
	if (len[ls[rt]]==mid-l+1) len[rt]=len[ls[rt]]+len[rs[rt]];
	    else len[rt]=len[ls[rt]];
}
void update(int &rt,int Rt,int l,int r,int x,int y){
	if (l==x&&r==y) {rt=Rt; return;}
	else{
		int trt=++cnt;
		ls[trt]=ls[rt],rs[trt]=rs[rt],rt=trt;
	}
    int mid=(l+r)>>1;
    if (y<=mid) update(ls[rt],ls[Rt],l,mid,x,y);
    else if (x>mid) update(rs[rt],rs[Rt],mid+1,r,x,y);
    else{
    	update(ls[rt],ls[Rt],l,mid,x,mid);
    	update(rs[rt],rs[Rt],mid+1,r,mid+1,y);
	}
	w[rt]=(w[ls[rt]]+1ll*w[rs[rt]]*two[mid-l+1]%mod)%mod;
	if (len[ls[rt]]==mid-l+1) len[rt]=len[ls[rt]]+len[rs[rt]];
	    else len[rt]=len[ls[rt]];
}
void add(int &Rt,int x){
	int now=zero(Rt,0,N,x,N);
	upd(Rt,0,N,now);
	if (xCnt||geq(heap[y].first,heap[y-1].first,0,N)) --y;
		if (geq(heap[x].first,heap[y].first,0,N)) swap(heap[x],heap[y]),x=y;
		    else break;
	}
}
void Push(pair x){
	heap[++Cnt]=x;
	for (int x=Cnt;x>1;x>>=1)
	if (geq(heap[x>>1].first,heap[x].first,0,N))
	    swap(heap[x],heap[x>>1]);
	else break;
}
void Dijkstra(int S){
	heap[Cnt=1]=make_pair(rt[S],S),build(rt[S],0,N);
	while (Cnt){
		while (Cnt&&v[heap[1].second]) Pop();
		if (!Cnt) return;
		int x=heap[1].second; v[x]=1,Pop();
		for (int i=as[x],Rt;i;i=e[i].next)
		if (!v[e[i].y]){
			int CNT=cnt;
			add(Rt=rt[x],e[i].w);
			if (!rt[e[i].y]||geq(rt[e[i].y],Rt,0,N)){
				rt[e[i].y]=Rt,pre[e[i].y]=x;
				Push(make_pair(Rt,e[i].y));
			}else for (;cnt>CNT;--cnt) w[cnt]=len[cnt]=ls[cnt]=rs[cnt]=0;
		}
	}
}
int main(){
	n=iut(),m=iut(),two[0]=1;
	if (n==1) return !printf("0\n1\n1");
	for (int i=1;i<=N;++i) two[i]=2ll*two[i-1]%mod;
	for (int i=1;i<=m;++i){
		int x=iut(),y=iut(),w=iut();
		e[++et]=(node){y,w,as[x]},as[x]=et;
		e[++et]=(node){x,w,as[y]},as[y]=et;
	}
	S=iut(),T=iut(),Dijkstra(S);
	if (pre[T]){
		for (int _T=T;_T;_T=pre[_T]) st[++Top]=_T;
		printf("%d\n%d\n",w[rt[T]],Top);
		for (int i=Top;i;--i)
		    printf("%d%c",st[i],i==1?10:32);
	}else printf("-1");
	return 0;
}