自动搬运

查看原文

来自洛谷，原作者为

	囧仙 你做东方鬼畜音MAD，好吗？

搬运于2025-08-24 22:36:10，当前版本为作者最后更新于2022-02-09 19:33:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题解

$\textbf{Subtask 1}$

容易发现一条边走多次总是不优的。因此可以直接暴力 $\text{dfs}$。

$\textbf{Subtask 2}$

用来给选手确认一下题意是否理解正确，因此设置了这个相当于是骗分的点。

$\textbf{Subtask 3 \& 4}$

开始进入正题。考虑一条边究竟会对最终的结果产生多大的贡献。容易发现，一条边产生的贡献会受到这条边之后的边对 $\text{tag}$ 的更新的影响。因此正着推是非常困难的（无法消除后效性）。不妨反过来想，只要知道了从一个点到达终点到底有哪些位置被更新了 $\text{tag}$，就可以很好地计算出 $w_i$ 产生的贡献的次数。

于是可以把所有的边反过来然后 $\text{dp}$，对于点 $i$ 记录一个状态 $u$，表示从它到达终点会有哪些节点会被产生更新。更新过程有这样一个特点：每次更新是自上而下的，下边某个节点的向下更新肯定是在它父亲节点向下更新之后。同时还有一个特点，每当一个带有 $\text{tag}$ 的节点向下更新后，带有这个 $\text{tag}$ 的节点个数恰好会增加 $1$ 个。但是会有一些实现细节上的问题，这也就区分了这两个 $\text{Subtask}$。

值得注意的是，所有的叶子节点是不会被更新的，因此维护的状态不需要存储最底下这一层，下文把非叶节点称作有效节点。也就是下图当中红色的部分。

首先使用 $\text{dfs}$ 对有效节点进行编号。记有效节点个数为 $s$，那么 $s$ 大约是 $k$ 左右。可以发现有效节点可以进行状压，放到一个 $\text{unsigned}$ 里边。对于这两个 $\text{Subtask}$，图上是一个 $\text{DAG}$，因此可以按照拓扑排序的顺序进行处理。对于每条边 $(u_i,v_i,l_i,r_i,w_i)$，考虑枚举 $v_i$ 的状态（设枚举的状态为 $y$），由此更新出 $u_i$ 对应状态的结果（设为 $x$）。那么我们需要计算这两个东西：

• $[l_i,r_i]$ 作用于线段树上会给多少个节点打上 $\text{tag}$。记为 $\mathit{num}_{l,r}$。
• $[l_i,r_i]$ 作用于线段树上后，哪些节点向下更新会导致 $w_i$ 贡献次数 $+1$。记为 $\mathit{A}_{l,r}$。
• $[l_i,r_i]$ 作用于线段树上会推动哪些节点向下更新 $\text{tag}$。记为 $\mathit{B}_{l,r}$。

其中 $A_{l,r}$ 和 $B_{l,r}$ 都是状态压缩后的状态。由于 $1\le l_i\le r_i\le k$，因此可以直接 $k^3$ 暴力预处理出这三个东西。放一个例子：

这张图展现了 $(2,6)$ 这样一条边的情况。我们应该预处理出被标成浅蓝色的这些节点所组成的状态为 $A_{l,r}$，深蓝色的节点组成的状态为 $B_{l,r}$。同时还需要计算出这条边实际给多少个节点打上了 $\text{tag}$，这个例子当中是 $2$（$[2,5)$ 和 $[5,7)$）。要注意，统计 $\mathit{num}_{l,r}$ 时不能忽略叶子节点被打上 $\text{tag}$ 的情况（这个例子里没有出现这样的情况而已）。

$(u,v,l,r,w)$ 是原图上的一条边。现在是 $\mathit{dp}$ 的一个更新过程。此时 $v$ 的状态为 $y$，边权为 $(l,r,w)$。现在需要从 $v:y$ 反向向前推导出 $u:x$ 并更新。重申一下这里记号的含义：$y$ 表示从 $v$ 到中点，会有哪些有效节点向下更新；$A_{l,r}$ 记录的是哪些有效节点被更新会导致 $w$ 的贡献次数 $+1$；$B_{l,r}$ 记录的是 $[l,r]$ 作用于线段树上会有哪些有效节点向下更新；$\mathit{num}_{l,r}$ 记录的是 $[l,r]$ 作用于线段树上会给多少个节点打上 $\text{tag}$。那么可以得到，$x=y\operatorname{or} B_{l,r}$，同时该边产生的贡献为 $w_i\cdot(\operatorname{popcount}(y\operatorname{and} A_{l,r})+\mathit{num}_{l,r})$。因此有：

$$\mathit{dp}_{u,y\operatorname{or} B_{l,r}}\gets\min\{\mathit{dp}_{u,y\operatorname{or} B_{l,r}},\mathit{dp}_{v,y}+w_i\cdot(\operatorname{popcount}(y\operatorname{and} A_{l,r})+\mathit{num}_{l,r})\} $$

其中 $\operatorname{popcount}(x)$ 表示 $x$ 在二进制下 $1$ 的个数。一种快速的实现方法是，预处理出 $0\sim 255$ 中每个数字二进制下 $1$ 的个数记为 $\mathit{pop}_0(x)$，那么 $\operatorname{popcount}(x)$ 就等于把 $x$ 分成四部分（用位运算实现）分别取 $\mathit{pop}_0$ 数组得到结果相加。这样复杂度几乎可以认为是常数。当然也可以用一些内置函数。

如果直接暴力枚举 $2^k$ 种状态，那么时间复杂度应当是 $\mathcal O(k^3+2^{k-1}\cdot m)$ 的，可以通过 $\text{Subtask 3}$。但可以发现一些状态是不可能实现的（诸如一个有效节点所对应的二进制值为 $1$，而它的父亲节点对应的二进制值却是 $0$）。我们称可以实现的状态为有效状态。考虑怎么计算长度为 $k$ 的线段树的有效状态总个数。

设 $f(x)$ 为长度为 $x$ 对应的线段树的非空的有效状态数。容易发现，

$$f(x)=\begin{cases} 0 & x\le 1 \cr (f(\lfloor\frac{x}{2}\rfloor)+1)\cdot (f(\lceil\frac{x}{2}\rceil)+1) & x> 1 \end{cases} $$

经过计算，可以得到 $f(\left.s\right|_{k=30})\approx 1.74\times 10^5$，这是远远小于 $2^{\left.s\right|_{k=30}}\approx 2.68\times 10^8$ 的。（$\left.s\right|_{k=30}=28$）下一步是如何枚举出所有有效状态。

这一步并不太难。你可以仿照 $\text{dp}$ 计算有效状态数的方法递归地计算出所有状态，但是比较麻烦。这里提供另外一种简单粗暴的方案。直接用 $\text{dfs}$ 依次枚举 $0\sim s-1$ 位应当是填充 $0$ 还是 $1$。当某个节点的父亲节点为 $\bm 0$，则该节点只能填 $\bm 0$。经过这样一个剪枝可以剪掉所有无用方案而恰好保留所有有效状态，复杂度是 $\mathcal O(f(s))$。

总时间复杂度为 $\mathcal O(f(s)\cdot m)$，空间复杂度为 $\mathcal O(f(s)\cdot n)$。

$\textbf{Subtask 5 \& 6}$

小清新 $\text{Subtask}$。可以发现瓶颈在于该子任务不再是有向无环图。

使用分层图，将每个点拆成 $f(s)$ 个点，每个点对应于一个状态。按照刚刚 $\text{dp}$ 的方式进行连边，总共连了 $f(s)\cdot m$ 条边。如果你直接使用堆优化 $\text{Dijsktra}$ 跑最短路，复杂度上会多一只 $\log$。但是可以发现本题答案不超过 $n\cdot 2k\cdot \max\{w_i\}$，估摸一下最大为 $50\cdot 60\cdot 10^3=3\times 10^5$，因此可以直接上桶排。复杂度降为 $\mathcal O(f(s)\cdot m)$。

总时间复杂度分析：

• 使用 $\mathcal O(k)$ 的复杂度计算出所有有效节点的标号。
• 使用 $\mathcal O(f(s))$ 的复杂度计算出所有有效状态。
• 使用 $\mathcal O(k^3)$ 暴力预处理出所有可能的 $(l,r)$ 对应的 $A,B,\mathit{num}$。
• 建立分层图跑最短路，复杂度为 $\mathcal O(f(s)\cdot m)$。

然而如果你先连边再跑最短路，空间复杂度达到了惊人的 $\mathcal O(f(s)\cdot m)$，然后发现你只能过 $\text{Subtask 5}$。但是完全可以在计算最短路的同时进行边的生成，此时空间复杂度降到了 $\mathcal O(n\cdot f(s))$，可以通过本题。

参考代码

#include<bits/stdc++.h>
#define up(l,r,i) for(int i=l,END##i=r;i<=END##i;++i)
#define dn(r,l,i) for(int i=r,END##i=l;i>=END##i;--i)
using namespace std;
typedef long long i64;
const int INF =2147483647;
typedef unsigned int       u32;
typedef unsigned long long u64;
namespace Hsh{
    const int SIZ =3e6-3;
    int H[SIZ],N[SIZ],W[SIZ],t; u32 V[SIZ];
    void add(int u,u32 v,int w){
        V[++t]=v,W[t]=w,N[t]=H[u],H[u]=t;
    }
    int get(u32 w){
        for(int i=H[w%SIZ];i;i=N[i]) if(V[i]==w) return W[i];
        return 0;
    }
}
namespace IIT{
    const int MAXN=16261+3,MAXS=32+3;
    int L[MAXS],R[MAXS],P[MAXS],Q[MAXS],F[MAXS],s,g;
    u32 A[MAXS][MAXS],B[MAXS][MAXS],N[MAXS][MAXS],C[MAXN];
    map<u32,int> M;
    int bld(int t,int l,int r){
        L[t]=l,R[t]=r; if(l!=r){
            int c=l+r>>1;
            if(l!=c  ) P[t]=bld(++s,l,c  ),F[P[t]]=t;
            if(r!=c+1) Q[t]=bld(++s,c+1,r),F[Q[t]]=t;
        }
        return t;
    }
    int T[MAXS],o;
    void clc(int t,int l,int r){
        if(l<=L[t]&&R[t]<=r){T[t]=-1,++o;} else {
            int c=L[t]+R[t]>>1; T[t]=1;
            if(l<=c&&P[t]) clc(P[t],l,r); else if(l<=c) ++o;
            if(r> c&&Q[t]) clc(Q[t],l,r); else if(r> c) ++o;
        }
    }
    void dfs(int x,u32 u,int k){
        if(x==s+1) {C[++g]=u,Hsh::add(u%Hsh::SIZ,u,g); return;}
        if(u&(1u<<F[x])) dfs(x+1,u|1u<<x,k);
        dfs(x+1,u,k);
    }
    void iit(int k){
        bld(0,1,k),dfs(1,1,k);
        up(1,k,i) up(i,k,j){
            memset(T,0,sizeof(T)),clc(0,i,j);
            N[i][j]=o,o=0; up(0,s,x){
                if(T[F[x]]==-1) T[x]=-1;
                if(T[x]==-1) A[i][j]|=1u<<x;
                if(T[x]== 1) B[i][j]|=1u<<x;
            }
        }
    }
}
namespace Lst{
    const int MAXN =4e6+3,SIZ =2e7+3;
    int H[MAXN],V[SIZ],N[SIZ],t;
    void add(int u,int v){
        V[++t]=v,N[t]=H[u],H[u]=t;
    }
}
namespace Gra{
    const int MAXN=1000+3,MAXM=3000+3;
    const int SIZ =16261+3;
    int H[MAXN],V[MAXM],T[MAXM],L[MAXM],R[MAXM],W[MAXM],s,t;
    void add(int u,int v,int l,int r,int w){
        V[++t]=v,L[t]=l,R[t]=r,W[t]=w,T[t]=H[u],H[u]=t;
    }
    const int MAXW=65536;
    int D[MAXN*SIZ],G[MAXW];
    int ppc(u32 u){
        return G[u>>16]+G[u&0xFFFF];
    }
    int dij(int a,int b){
        using IIT::g; using IIT::C; using IIT::A;
        using IIT::B; using IIT::M; using IIT::N;
        up(0,65535,i) G[i]=G[i>>1]+(i&1); Lst::add(1,b*(g+1));
        up(1,Lst::MAXN,d) for(int oo=Lst::H[d];oo;oo=Lst::N[oo]){
            int o=Lst::V[oo]; if(D[o]&&D[o]<d) continue; D[o]=d;
            int u=o/(g+1),x=o%(g+1); if(u==a) return d-1;
            for(int i=H[u];i;i=T[i]){
                int v=V[i],l=L[i],r=R[i],y=Hsh::get(C[x]|B[l][r]);
                int w=W[i]*(ppc(C[x]&A[l][r])+N[l][r]);
                int p=v*(g+1)+y;
                if(D[p]>d+w||!D[p]) Lst::add(d+w,p),D[p]=d+w;
            }
        }
        return -1;
    }
}
namespace Slv{
    const int MAXN=1000+3,MAXM=16261+3,MAXK=3000+3;
    int U[MAXK],V[MAXK],L[MAXK],R[MAXK],K[MAXK];
    int qread(){
        int w=1,c,ret;
        while((c=getchar())> '9'||c< '0') w=(c=='-'?-1:1); ret=c-'0';
        while((c=getchar())>='0'&&c<='9') ret=ret*10+c-'0';
        return ret*w;
    }
    int n,m,k,a,b,t,ans=1e9;
    void mian(){
        n=qread(),m=qread(),k=qread(),a=qread(),b=qread(); IIT::iit(k);
        up(1,m,i){
            int u=qread(),v=qread(),l=qread(),r=qread(),w=qread();
            Gra::add(v,u,l,r,w);
        }
        printf("%d\n",Gra::dij(a,b));
    }
}
int main(){
#ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
#endif
    Slv::mian(); return 0;
}