CF464E The Classic Problem

题意

给定一张图，边权为 \(2^x,x\le 10^5\)，求 \(s\) 到 \(t\) 的最短路以及方案。

Solution

直接上最短路！现在的问题是如何高效存储路径上权值的加和。这题有个特殊之处就是边权都是二的整次幂，我们需要一个有效的方式来实现手动二进制进位并且能够保证时空复杂度。

这题我们利用线段树+哈希的套路来维护每个点的权值。注意到 Dij 在做的时候实际上只需要能够做加法，能够比较大小就可以了。于是我们对于每个点维护一个动态开点线段树，然后线段树上维护二进制位上一段区间中的二进制哈希值，也就是二进制的值模上 \(10^9+7\)。

接下来解决比较的问题。实际上我们是在二进制位上从高到低找到第一个不同的。这样我们利用每个节点的哈希值能够比较两个值是否相同，直接在线段树上二分就可以了，比较复杂度是 \(O(\log n)\) 的。

接下来解决加法的问题。会在二进制位上单点加，这样的话实际上我们是找到一个最小的 \(y\) 使得 \(y\ge x\)，并且 \(y\) 位上是 \(0\)。这样的话，我们实际上就是在 \(y\) 单点加，而在 \([x,y)\) 区间覆盖为 \(0\)。\(y\) 可以用线段树上二分方便找到。

接下来是一些实现的细节。在最短路的权值记录的时候，我们只对每个点记录它所对应的线段树的根。然后在跑最短路的过程中，会得到一棵最短路生成树，可以用主席树来维护。

Code

// Problem: 
//     The Classic Problem
//   
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF464E
// Memory Limit: 750 MB
// Time Limit: 5000 ms

#include<bits/stdc++.h>
#define ll long long
#define inf (1<<30)
#define INF (1ll<<60)
#define pb emplace_back
#define pii pair<int,int>
#define mkp make_pair
#define fi first
#define se second
#define all(a) a.begin(),a.end()
#define siz(a) (int)a.size()
#define clr(a) memset(a,0,sizeof(a))
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define pt(a) cerr<<#a<<'='<<a<<' '
#define pts(a) cerr<<#a<<'='<<a<<'\n'
#define int long long
using namespace std;
const int MAXN=1e5+110;
const int MOD=1e9+7;
int pw2[MAXN];
void init(){pw2[0]=1;rep(i,1,MAXN-10) pw2[i]=pw2[i-1]*2%MOD;}

struct Tree{int ls,rs,siz,hsh,cnt;}tr[MAXN*80];
#define ls(i) tr[i].ls
#define rs(i) tr[i].rs
int tot;
void build(int &i,int l=0,int r=MAXN-10){
	i=++tot;tr[i].siz=r-l+1;if(l==r){tr[i].hsh=tr[i].cnt=0;return;}
	int mid=(l+r)>>1; build(ls(i),l,mid);build(rs(i),mid+1,r);
}
void pushup(int i){
	tr[i].cnt=tr[ls(i)].cnt+tr[rs(i)].cnt;
	tr[i].hsh=(tr[ls(i)].hsh+tr[rs(i)].hsh*pw2[tr[ls(i)].siz]%MOD)%MOD;
}
void add(int &i,int lst,int x,int l=0,int r=MAXN-10){
	i=++tot;tr[i]=tr[lst];if(l==r){tr[i].cnt++;tr[i].hsh++;return;}int mid=(l+r)>>1;
	if(x<=mid) add(ls(i),ls(lst),x,l,mid);else add(rs(i),rs(lst),x,mid+1,r);pushup(i);
}
void cov(int &i,int lst,int L,int R,int org=1,int l=0,int r=MAXN-10){
	if(L==l&&r==R){i=org;return;}i=++tot;tr[i]=tr[lst];int mid=(l+r)>>1;
	if(R<=mid) cov(ls(i),ls(lst),L,R,ls(org),l,mid);else if(L>mid) cov(rs(i),rs(lst),L,R,rs(org),mid+1,r);
	else cov(ls(i),ls(lst),L,mid,ls(org),l,mid),cov(rs(i),rs(lst),mid+1,R,rs(org),mid+1,r);pushup(i);
}
bool comp(int a,int b,int l=0,int r=MAXN-10){
	if(a==b) return 0;if(l==r) return tr[a].hsh>tr[b].hsh;int mid=(l+r)>>1;
	if(tr[rs(a)].hsh==tr[rs(b)].hsh) return comp(ls(a),ls(b),l,mid);
	else return comp(rs(a),rs(b),mid+1,r);
}
int ask(int i,int L,int R,int l=0,int r=MAXN-10){
	if(l==L&&r==R) return tr[i].cnt;int mid=(l+r)>>1;
	if(R<=mid) return ask(ls(i),L,R,l,mid);else if(L>mid) return ask(rs(i),L,R,mid+1,r);
	else return ask(ls(i),L,mid,l,mid)+ask(rs(i),mid+1,R,mid+1,r);
}
int find(int i,int x,int rem,int l=0,int r=MAXN-10){
	if(l==r) return l;int mid=(l+r)>>1;
	if(x>mid) return find(rs(i),x,rem-tr[ls(i)].cnt,mid+1,r);
	if(x<l){
		if(tr[ls(i)].cnt==tr[ls(i)].siz) return find(rs(i),x,rem,mid+1,r);
		else return find(ls(i),x,rem,l,mid);
	}
	if(tr[ls(i)].cnt-rem==mid-x+1) return find(rs(i),x,0,mid+1,r);
	else return find(ls(i),x,rem,l,mid);
}
void upd(int pre,int &i,int x){
	int rem=0;if(x) rem=ask(pre,0,x-1);
	int y=find(pre,x,rem);
	if(x!=y) cov(i,pre,x,y-1);else i=pre;add(i,i,y);
}

struct Edge{int to,w;};
vector<Edge> e[MAXN];
int dis[MAXN],pre[MAXN];
struct node{
	int x,dis;
	bool friend operator<(node a,node b){return comp(a.dis,b.dis);}
};
priority_queue<node> q;
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	init();
	int n,m;cin>>n>>m;
	rep(i,1,m){
		int u,v,x;cin>>u>>v>>x;
		e[u].pb(Edge{v,x});e[v].pb(Edge{u,x});
	}
	int S,T;cin>>S>>T;
	build(dis[S]);
	q.push(node{S,dis[S]});
	while(!q.empty()){
		node now=q.top();q.pop();
		if(dis[now.x]&&comp(now.dis,dis[now.x])) continue;
		for(auto s:e[now.x]){
			node nxt;nxt.x=s.to;
			upd(now.dis,nxt.dis,s.w);
			if(!dis[nxt.x]||comp(dis[nxt.x],nxt.dis)){
				pre[nxt.x]=now.x;
				dis[nxt.x]=nxt.dis;
				q.push(nxt);
			}
		}
	}
	if(!dis[T]){
		cout<<-1<<'\n';
		return 0;
	}
	cout<<tr[dis[T]].hsh<<'\n';
	vector<int> pth;
	while(T) pth.pb(T),T=pre[T];
	reverse(all(pth));
	cout<<siz(pth)<<'\n';
	for(int p:pth) cout<<p<<' ';
	return 0;
}