题目大意
给定一张$n$个点, $m$条边的无向图,求$S$ 到$T$的最短路,其中边权都是$2^k$的形式$n,m,k<=10^5$，结果对$10^9+7$取模
题解
大佬好厉害
跑一边dijstra大家应该都想的到
但问题是维护最短路的距离怎么实现
我太菜了除了python啥都想不到
我们可以把距离拆成每一位，因为每一次只会加上一个数，直接开主席树维护就好了
时间复杂度什么的……感性理解一下就好了
比较大小直接二分哈希
//minamoto
#include<bits/stdc++.h>
using namespace std;
#define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[<<],*p1=buf,*p2=buf;
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,:;}
inline int read(){
#define num ch-'0'
char ch;bool flag=;int res;
while(!isdigit(ch=getc()))
(ch=='-')&&(flag=true);
for(res=num;isdigit(ch=getc());res=res*+num);
(flag)&&(res=-res);
#undef num
return res;
}
const int N=1e5+,mod=1e9+;
int n,m,head[N],Next[N<<],ver[N<<],edge[N<<];
int S,T,lim,b[N<<],rt[N],Pre[N],tot,cnt;
int L[N*],R[N*],sum[N*];
inline void add(int u,int v,int e){
ver[++tot]=v,Next[tot]=head[u],head[u]=tot,edge[tot]=e;
ver[++tot]=u,Next[tot]=head[v],head[v]=tot,edge[tot]=e;
}
bool cmp(int u,int v,int l,int r){
if(l==r) return sum[u]>sum[v];
int mid=(l+r)>>;
if(sum[R[u]]==sum[R[v]]) return cmp(L[u],L[v],l,mid);
else return cmp(R[u],R[v],mid+,r);
}
int update(int last,int &now,int l,int r,int k){
L[now=++cnt]=L[last],R[now]=R[last];
if(l==r){
sum[now]=sum[last]^;
return sum[last];
//每一个节点存的只有一位，如果加之前是1就要进位
}
int mid=(l+r)>>,res;
if(k>mid) res=update(R[last],R[now],mid+,r,k);
else{
res=update(L[last],L[now],l,mid,k);
if(res) res=update(R[last],R[now],mid+,r,k);
}
sum[now]=(1ll*sum[R[now]]*b[mid-l+]+sum[L[now]])%mod;
return res;
}
struct node{
int x,rt;
bool operator <(const node &b)const
{return cmp(rt,b.rt,,lim);}
};
priority_queue<node> q;
void dfs(int u,int dep){
if(u==S){printf("%d\n%d ",dep,u);return;}
dfs(Pre[u],dep+);
printf("%d ",u);
}
void print(int u){
printf("%d\n",sum[rt[u]]);
dfs(u,);exit();
}
int main(){
//freopen("testdata.in","r",stdin);
n=read(),m=read();
for(int i=;i<=m;++i){
int u,v,e;
u=read(),v=read(),e=read();
add(u,v,e);
cmax(lim,e);
}
lim+=;
b[]=;for(int i=;i<=lim;++i) b[i]=(1ll*b[i-]<<)%mod;
S=read(),T=read();
q.push((node){S,rt[S]});
while(!q.empty()){
node u=q.top();q.pop();
if(u.rt!=rt[u.x]) continue;
//如果不一样，说明已经在主席树上被修改了
//就给普通的判dijkstra一样就好了
if(u.x==T) print(T);
for(int i=head[u.x];i;i=Next[i]){
int v=ver[i],RT;
update(u.rt,RT,,lim,edge[i]);
if(!rt[v]||cmp(rt[v],RT,,lim))
rt[v]=RT,q.push((node){v,rt[v]}),Pre[v]=u.x;
}
}
puts("-1");
return ;
}