题目大意

给定一张$n$个点, $m$条边的无向图,求$S$ 到$T$的最短路,其中边权都是$2^k$的形式$n,m,k<=10^5$，结果对$10^9+7$取模

 

题解

好厉害

跑一边dijstra大家应该都想的到

但问题是维护最短路的距离怎么实现

我太菜了除了python啥都想不到

我们可以把距离拆成每一位，因为每一次只会加上一个数，直接开主席树维护就好了

时间复杂度什么的……感性理解一下就好了

比较大小直接二分哈希

1 //minamoto 2 #include
     
       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
      
       inline bool cmax(T&a,const T&b){
   return a
       
        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)const50     {
   return cmp(rt,b.rt,0,lim);}51 };52 priority_queue
        
          q;53 void dfs(int u,int dep){54     if(u==S){printf("%d\n%d ",dep,u);return;}55     dfs(Pre[u],dep+1);56     printf("%d ",u);57 }58 void print(int u){59     printf("%d\n",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 }