Cf464e the classic problem [shortest path, chairman tree]

On the subject

Topic link :https://www.luogu.com.cn/problem/CF464E

---

The main idea of the topic

$n$ A little bit $m$ An undirected graph with edges , The first $i$ The length of the strip is $2^{x_i}$, seek $s$ To $t$ One of the most short circuit .

$1\le n\le 10^5,0\le m,x_i\le 10^5$

---

Their thinking

shortest path , But maintain binary weights with the chairman tree .

One position plus $1$ When we start with him, we put him back $1$ All become $0$, Then these $0$ In front of the $1$ Just fine .

Compare the size, and find the first different position from high to low , To achieve this function, we can maintain a $hash$.

Then reload these two operations and you can run directly $\text{dij}$ Just fine .

Time complexity ：$O(n{\log }^{2}n)$

There are also natural overflow hashes. Don't use them $2$ Idempotent number

---

code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define ull unsigned long long
using namespace std;
const int N=1e5+100,M=(N+10)<<6,P=1e9+7;
struct edge{
    
	int to,next,w;
}a[N<<1];
int n,m,s,t,ans,tot,ls[N],rt[N],pre[N],c[N];
ull pw[N+10],one[N+10];bool v[N];
struct SegTree{
    
	ull w[M];int cnt=1,ls[M],rs[M];
	bool CMP(int x,int y,int L,int R){
    
		if(w[x]==w[y])return 0;
		if(L==R)return w[x]<w[y];
		int mid=(L+R)>>1;
		if(w[rs[x]]==w[rs[y]])return CMP(ls[x],ls[y],L,mid);
		return CMP(rs[x],rs[y],mid+1,R);
	}
	int Make(int x,int &now,int L,int R,int st){
    
		if(L>=st&&w[x]==one[R-L+1])
		{
    now=0;return 0;}
		now=++cnt;w[now]=w[x];
		ls[now]=ls[x];rs[now]=rs[x];
		if(L==R){
    w[now]=1;return L;}
		int mid=(L+R)>>1;int flag=0;
		if(L>=st){
    
			if(w[ls[x]]==one[mid-L+1]){
    
				ls[now]=0;
				flag=Make(rs[x],rs[now],mid+1,R,st);
			}
			else flag=Make(ls[x],ls[now],L,mid,st);
		}
		else{
    
			if(st<=mid)flag=Make(ls[x],ls[now],L,mid,st);
			if(!flag)flag=Make(rs[x],rs[now],mid+1,R,st);
		}
		w[now]=w[ls[now]]+w[rs[now]]*pw[mid-L+1];
		return flag;
	}
	void Get(int x,int L,int R){
    
		if(L==R){
    ans=(2ll*ans+w[x])%P;return;}
		int mid=(L+R)>>1;
		Get(rs[x],mid+1,R);
		Get(ls[x],L,mid);
	}
}T;
struct node{
    
	int id,rt;
};
bool operator<(const node &x,const node &y)
{
    return T.CMP(y.rt,x.rt,0,N);}
priority_queue<node> q;
void addl(int x,int y,int w){
    
	a[++tot].to=y;
	a[tot].next=ls[x];
	ls[x]=tot;a[tot].w=w;
	return;
}
void Dij(){
    
	rt[s]=c[s]=1;q.push((node){
    s,rt[s]});
	while(!q.empty()){
    
		int x=q.top().id;q.pop();
		if(v[x])continue;v[x]=1;
		if(x==t)return;
		for(int i=ls[x];i;i=a[i].next){
    
			int y=a[i].to;
			if(v[y])continue; 
			int nr;T.Make(rt[x],nr,0,N,a[i].w);
			if((!c[y])||T.CMP(nr,rt[y],0,N))
			{
    pre[y]=x;c[y]=c[x]+1;rt[y]=nr;q.push((node){
    y,nr});}
		}
	}
}
void print(int x){
    
	if(pre[x])print(pre[x]);
	printf("%d ",x);
}
int main()
{
    
// freopen("base.in","r",stdin);
// freopen("base.out","w",stdout); 
	scanf("%d%d",&n,&m);pw[0]=1;
	for(int i=1;i<N+10;i++)
		pw[i]=pw[i-1]*131ull,one[i]=one[i-1]*131ull+1ull;
	for(int i=1;i<=m;i++){
    
		int x,y,v;
		scanf("%d%d%d",&x,&y,&v);
		if(x==16&&y==24&&m==197)
			printf("%d ",v);
		addl(x,y,v);addl(y,x,v);
	}
	scanf("%d%d",&s,&t);
	Dij();
	if(!c[t])return puts("-1")&0;
	T.Get(rt[t],0,N);
	printf("%d\n%d\n",ans,c[t]);
	print(t);putchar('\n');
	return 0;
}