题目大意
给定一张$n$个点, $m$条边的无向图,求$S$ 到$T$的最短路,其中边权都是$2^k$的形式$n,m,k<=10^5$，结果对$10^9+7$取模
题解
大佬好厉害
跑一边dijstra大家应该都想的到
但问题是维护最短路的距离怎么实现
我太菜了除了python啥都想不到
我们可以把距离拆成每一位，因为每一次只会加上一个数，直接开主席树维护就好了
时间复杂度什么的……感性理解一下就好了
比较大小直接二分哈希
1 //minamoto 2 #include<bits/stdc++.h> 3 using namespace std; 4 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 5 char buf[1<<21],*p1=buf,*p2=buf; 6 template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;} 7 inline int read(){ 8 #define num ch-'0' 9 char ch;bool flag=0;int res; 10 while(!isdigit(ch=getc())) 11 (ch=='-')&&(flag=true); 12 for(res=num;isdigit(ch=getc());res=res*10+num); 13 (flag)&&(res=-res); 14 #undef num 15 return res; 16 } 17 const int N=1e5+5,mod=1e9+7; 18 int n,m,head[N],Next[N<<1],ver[N<<1],edge[N<<1]; 19 int S,T,lim,b[N<<1],rt[N],Pre[N],tot,cnt; 20 int L[N*120],R[N*120],sum[N*120]; 21 inline void add(int u,int v,int e){ 22 ver[++tot]=v,Next[tot]=head[u],head[u]=tot,edge[tot]=e; 23 ver[++tot]=u,Next[tot]=head[v],head[v]=tot,edge[tot]=e; 24 } 25 bool cmp(int u,int v,int l,int r){ 26 if(l==r) return sum[u]>sum[v]; 27 int mid=(l+r)>>1; 28 if(sum[R[u]]==sum[R[v]]) return cmp(L[u],L[v],l,mid); 29 else return cmp(R[u],R[v],mid+1,r); 30 } 31 int update(int last,int &now,int l,int r,int k){ 32 L[now=++cnt]=L[last],R[now]=R[last]; 33 if(l==r){ 34 sum[now]=sum[last]^1; 35 return sum[last]; 36 //每一个节点存的只有一位，如果加之前是1就要进位 37 } 38 int mid=(l+r)>>1,res; 39 if(k>mid) res=update(R[last],R[now],mid+1,r,k); 40 else{ 41 res=update(L[last],L[now],l,mid,k); 42 if(res) res=update(R[last],R[now],mid+1,r,k); 43 } 44 sum[now]=(1ll*sum[R[now]]*b[mid-l+1]+sum[L[now]])%mod; 45 return res; 46 } 47 struct node{ 48 int x,rt; 49 bool operator <(const node &b)const 50 {return cmp(rt,b.rt,0,lim);} 51 }; 52 priority_queue<node> q; 53 void dfs(int u,int dep){ 54 if(u==S){printf("%d %d ",dep,u);return;} 55 dfs(Pre[u],dep+1); 56 printf("%d ",u); 57 } 58 void print(int u){ 59 printf("%d ",sum[rt[u]]); 60 dfs(u,1);exit(0); 61 } 62 int main(){ 63 //freopen("testdata.in","r",stdin); 64 n=read(),m=read(); 65 for(int i=1;i<=m;++i){ 66 int u,v,e; 67 u=read(),v=read(),e=read(); 68 add(u,v,e); 69 cmax(lim,e); 70 } 71 lim+=100; 72 b[0]=1;for(int i=1;i<=lim;++i) b[i]=(1ll*b[i-1]<<1)%mod; 73 S=read(),T=read(); 74 q.push((node){S,rt[S]}); 75 while(!q.empty()){ 76 node u=q.top();q.pop(); 77 if(u.rt!=rt[u.x]) continue; 78 //如果不一样，说明已经在主席树上被修改了 79 //就给普通的判dijkstra一样就好了 80 if(u.x==T) print(T); 81 for(int i=head[u.x];i;i=Next[i]){ 82 int v=ver[i],RT; 83 update(u.rt,RT,0,lim,edge[i]); 84 if(!rt[v]||cmp(rt[v],RT,0,lim)) 85 rt[v]=RT,q.push((node){v,rt[v]}),Pre[v]=u.x; 86 } 87 } 88 puts("-1"); 89 return 0; 90 }