CF464E The Classic Problem 题解

· · 题解

CF464E The Classic Problem 题解

总体情况

大体仍是主席树+哈希，但在进位处理方面采用了压位优化，目前全谷最优解（2021.10.15）。

题意这里不再赘述

CF464E The Classic Problem

朴素思路

首先最短路可以想到 Dijkstra。

我们需要支持两个数比较大小和加法操作，但问题是边权范围太大无法直接储存，如果用高精度的话时间复杂度又会多一个 x，难以承受。

考虑优化

发现每次更新长度时，如一条 u\to v 的路径，可能会使 dis_v 成为 dis_u 加上 2 的次幂，如果在二进制下的话可以发现不考虑进位那么发生变化的只有一位。这个性质可以让我们想到用二进制的主席树来维护 dis。

比较大小

比较常见的问题，朴素地做即找到两个数从高到低第一个不一样的位置并且比较大小，这一步操作可以用哈希在线段树上二分来实现。

加法

刚才我们分析“只有一位产生变化”前提是不产生进位。对于进位，有一种做法即找到当前位置向高位最长的连续一段一并将其置零，下一个零的位置变成一，但这样可能维护较为麻烦并且较慢，考虑优化。

我们刚才提到一次只加一个 2 的次幂，那有个有趣的做法，即二进制压位，比如我们每 50 位压成一位，那么线段树每个点对应的区间就分别是 [0,49],[50,99],... 这种。

我们发现如果这样操作进位操作是非常少的，因为这样的话比如在 [0,49] 这个区间内最可能产生进位的操作是加上 2^{49}，但我们发现如果进位的话只会在 [50,99] 加上 1，这样的话在下一位几乎是不会产生进位的，除非下一个区间 50 位全都是 1，但这样也只会产生一次进位。

总而言之如果把 50 位压到一起的话进位操作就会非常少，实测这样速度快得飞起，当场冲到最优解。

实现细节

注意这里主席树比较的话是要创建新根的，也就是每次比较都会产生一定的空间消耗，那我们就要尽量减少比较次数。

每次我们把点入队时，可能还没处理就被再次入队，显然每次入队对应的根是不同的，我们在结构体里加一下入队时的根，如果和当前根不同说明被再次入队了，就可以直接跳过不进行计算，蒟蒻因为没加这个优化被卡了一个多小时（雾）。

最后

其实这种方法是可以被 Hack 掉的，比如可以从起点开始到某个点来一条链，边权依次 +1，然后在这个点再接个类似菊花图的东西，各点再连向终点，边权都是 2^0 就会被卡成 O(n^2\log n)。

不过善良的出题人并没有卡这种做法，实际上真的要卡的话加上找连续段也是可以通过的。如果不是很严格地来卡这种做法的话复杂度是很难退化的。

贴代码

#include <bits/stdc++.h>
#define lint long long
#define rint register int
using namespace std;
inline lint read(){
    char c;lint f=1,res=0;
    while(c=getchar(),!isdigit(c))if(c=='-')f*=-1;
    while(isdigit(c))res=res*10+c-'0',c=getchar();
    return res*f;
}
const int N=1e5+5,M=2e5+5,B=50,R=2e3+5,P=1e7+5;
const lint md=1e9+7,bas=2333333;
int hed[N],nxt[M],ver[M],w[M],ne=1;
inline void ade(int u,int v,int _w){
    ver[++ne]=v;
    nxt[ne]=hed[u];
    hed[u]=ne;
    w[ne]=_w;
}
inline void adbe(int u,int v,int _w)
    {ade(u,v,_w);ade(v,u,_w);}
int n,m,s,t;
int rt[N],tot=0;
lint ans=0,pw[B+1],_pw[R];
int ch[P][2],mx[P];
lint hsh[P],pwb[N],sum[P];
inline int cpy(int y){
    int x=++tot;
    if(y){
        memcpy(ch[x],ch[y],sizeof ch[x]);
        sum[x]=sum[y];mx[x]=mx[y];
    }else mx[x]=-1;
    return x;
}
inline lint qpow(lint x,lint y){
    lint res=1;
    while(y){
        if(y&1)res=res*x%md;
        x=x*x%md;y>>=1;
    }return res;
}
//sum只存在于最底层 
inline void pushup(int x,int l,int r){
    int lc=ch[x][0],rc=ch[x][1],mid=l+r>>1;
    mx[x]=max(mx[lc],mx[rc]);
    hsh[x]=(pwb[r-mid]*hsh[ch[x][1]]%md+hsh[ch[x][0]])%md;
}
void add(int x,int l,int r,int p,lint v){
    if(l==r){
        sum[x]+=v;hsh[x]=sum[x];
        if(sum[x])mx[x]=l;
        else mx[x]=-1;
        return;
    }int mid=l+r>>1;
    if(p<=mid)add(ch[x][0]=cpy(ch[x][0]),l,mid,p,v);
    else add(ch[x][1]=cpy(ch[x][1]),mid+1,r,p,v);
    pushup(x,l,r);
}
lint gsum(int x,int l,int r,int p){
    if(!x)return 0;
    if(l==r)return sum[x];
    int mid=l+r>>1;
    if(p<=mid)return gsum(ch[x][0],l,mid,p);
    else return gsum(ch[x][1],mid+1,r,p);
}
//获取整棵树答案对md取模的结果 
//编号从0开始，第零段对应 [0,49] 
lint gans(int x,int l,int r){
    if(!x||mx[x]==-1)return 0;
    if(l==r)return sum[x]%md*_pw[l]%md;
    lint mid=l+r>>1,res=0;
    res+=gans(ch[x][0],l,mid);
    res+=gans(ch[x][1],mid+1,r);
    return res%md;
}
//在u的根的基础上加上2^x产生一个新根 
inline int upd(int u,int x){
    int nrt=cpy(rt[u]);
    add(nrt,0,R,x/B,pw[x%B]);
    int p=x/B;lint tmp;
    while((tmp=gsum(nrt,0,R,p))>=pw[B]){
        add(nrt,0,R,p,tmp%pw[B]-tmp);
        add(nrt,0,R,p+1,tmp/pw[B]);
        ++p;
    }return nrt;
}
//返回x的值是否小于y 
bool les(int x,int y,int l,int r){
    if(mx[x]!=mx[y])return mx[x]<mx[y];
    if(l==r)return sum[x]<sum[y];
    int mid=l+r>>1;
    if(hsh[ch[x][1]]!=hsh[ch[y][1]])
        return les(ch[x][1],ch[y][1],mid+1,r);
    else return les(ch[x][0],ch[y][0],l,mid);
}
struct node{int id,rt;};
inline bool operator>(node x,node y)
    {return les(rt[y.id],rt[x.id],0,R);}
priority_queue<node,vector<node>,greater<node> > q;
int pre[N],rd[N],cnt;
inline void Dijkstra(){
    q.push(node{s,rt[s]});
    while(!q.empty()){
        node tp=q.top();
        q.pop();int u=tp.id;
        if(tp.rt!=rt[u])continue;
        for(rint e=hed[u];e;e=nxt[e]){
            int v=ver[e];
            int tmp=upd(u,w[e]);
            if(!rt[v]||les(tmp,rt[v],0,R)){
                rt[v]=tmp;pre[v]=u;
                q.push(node{v,rt[v]});
            }
        }
    }
    ep:if(!rt[t])ans=-1;
    else ans=gans(rt[t],0,R);
    int u=t;
    while(u){
        rd[++cnt]=u;
        u=pre[u];
    }
}
inline void init(){
    pw[0]=1;pwb[0]=1;
    for(rint i=1;i<=B;++i)
        pw[i]=pw[i-1]*2;
    for(rint i=1;i<N;++i)
        pwb[i]=pwb[i-1]*bas%md;
    _pw[0]=1;_pw[1]=qpow(2,B);
    for(rint i=1;i<R;++i)
        _pw[i]=_pw[i-1]*_pw[1]%md;
    rt[s]=++tot;mx[s]=-1;
}
int main(){
    n=read();m=read();
    for(rint i=1;i<=m;++i){
        int u=read(),v=read();
        int _w=read();
        adbe(u,v,_w);
    }
    s=read();t=read();
    init();Dijkstra();
    printf("%lld\n",ans);
    if(ans==-1)return 0;
    printf("%d\n",cnt);
    for(rint i=cnt;i>=1;--i)
        printf("%d ",rd[i]);
    return 0;
}