「Wdoi-1.5」旅人 1977

深邃的星空中划出了一道灿烂的弧线，而后又同这广袤境界溶为一体，二十世纪的旅行者，承载着期待与不安向着外太空飞去。这是一份来自一个遥远的小小世界的礼物。上面记载着我们的声音、我们的科学、我们的影像、我们的音乐、我们的思想和感情。我们正努力生活过我们的时代，进入你们的时代。或许人类将失去对它的联系，它也将像一个漂流瓶一样，向着宇宙深处孤独的走下去，直到被「另一个人」所捡起。而它为我们留下的最后一张「自拍」，也只是一个 $0.12$ 像素大的、淡蓝色的光点 —— 这是我们迄今所知的唯一家园。 $\kern{80pt}$ $$\\[-1em]\scriptscriptstyle\text{暗淡蓝点，旅行者 1 号，1990年 2 月 14 日}$$ 「已经分不清现实与梦境了呢。」 「或许，梦与现之间的境界，本就没有那么明晰。」 …… 「真是的，莲子你不是自称亲近星光与月亮的嘛，怎么也不抬头看看。」 正欲向笔记本上添加几行，借以目视的月光陡然暗淡。眼前垂落的金色长发挡住了我的视线。轻咳了一声，抬起手在面前挥舞，把他们从视野中赶走，我转头看着后背。 眼前戴着白色帽子的少女便是我的同伴梅莉。我常常打趣她有着奇异的眼睛，可以看到我们所看不到的「境界」。尽管我自己的眼睛也十分特殊——我有着通过星光与月亮就知道我们现处何时何地的能力。忘了说了，我们是学生秘密社团『秘封俱乐部』，专门探寻科学世纪下的隐藏结界。 在这个夏夜，我本着履行对她承诺的想法，来到野外，观察天体的运行。 「在想什么呢？」 这个问题不好回答呢。不过，既然今天和梅莉约好出来观赏星空，那么，思路被引向人们曾经的探索和求知，便是十分自然的了。 「唔，我在想，我们现今，科学世纪的起源。」 「嗯？莲子你不是研究物理的吗，怎么突然思考其这种问题了？」 梅莉把头朝右侧一歪，我指指天空，她随即坐在了一旁，把目光投向灿烂的星海。 「唔，我在想，我们现今，科学世纪的起源。还记得我和你说过的那两位旅人吗？」 「旅行者一号与旅行者二号？」 「没错。直到如今都没有人为任何深空计划取名为旅行者。带着如此诗意而感性名称的它们代表的是人们对未来的期许与对真理的渴望。面对未知与迷茫，义无反顾冲向了星海。」 梅莉站了起来，举起了双筒望远镜。她的身影在暗淡而幽静的夜色中来回移动，皎白得似有彩色光晕的月光从穹顶透过树叶与树枝的缝隙在她身上落下光斑，看着让人心醉。 超新星爆发是恒星生命的终点，也是新生恒星生命的起点。谁能说科学已经到了尽头，无法解释的事物不存在呢？科学的核心在于那些被视为空花阳焰，藏在迷雾中的东西，而绝非那些狂妄自大的老头们所说，科学是我们掌握的一切已知。 对我们而言，这是不言而喻的。我们追随那位初代社长的脚步，探寻遍布四处的结界，寻求隐藏在未知背后真理的一角，正是出于这样的信念。 晷刻渐移，点点星尘围绕着北极星作着圆周运动。仔细看的话，北极星也在微微运动。在我的视线前方，梅莉兴奋地对着从英仙座辐射而出，偶尔划过天穹的流星发出惊叹。我不禁思索起来，现在勾陈一作为最接近北天极的恒星行使着为旅人指点方向的责任，但在永恒的运动中，永远会有新的谜题，新的未知，新的探索等着我们去发现。 物如此，事犹是，人亦然。前路永远有着未知的事物等着我们去探索。如果解明了所有的秘密，之后就会什么都不剩。知晓万物什么的，只不过是空空如也的虚无罢了。未知，才是驱动人类的原动力 $\scriptscriptstyle{}^{[{\color{grey}{1}}]}$。我们希冀着如同那两位先行者一般，作为开拓者，唤起根植于人们心中对未知的好奇与探索精神，并将它薪火相传。 身虽位于苍穹一粟，心亦向往若尘繁星。 身旁的梅莉靠在一棵树下，已经发出规律的鼾声，身体规律地微微起伏着。我伸手拨开她的手掌，撩开她垂下的头发，拿出她的笔记本。 >从夜晚走向清晨。 从清晨走向夜晚。 从现实走向梦境。 从梦境走向现实。 终有一天，我们会在梦中，邂逅那片未经观测的星空。$\scriptscriptstyle{}^{[{\color{grey}{2}}]}$ $\scriptscriptstyle{[1],[2]}\text{：引用自 }$ [here](https://bbs.nyasama.com/forum.php?mod=viewthread&tid=308054&page=2)

深邃的星空可以被视作一张有向图，图上的节点就是点点恒星。点无点权，边有边权。图的点数为 $n$，边数为 $m$，图可能有重边自环。但保证至少有一条路径可以从 $s$ 走到 $t$（$s$、$t$ 在输入中给定）。第 $i$ 条有向边起点为 $u_i$，终点为 $v_i$，它的权值用一个有序三元组 $(l_i,r_i,w_i)$ 表示。 莲子要从点 $s$ 出发，经过了若干条边到达点 $t$。她带有一个初始值均为 $0$ 的长度为 $k$ 的数组 $a$，每次经过编号为 $i$ 的边，就会执行将 $a$ 数组的区间 $[l_i,r_i]$ 加 $w_i$ 的操作。她使用了一棵**带懒标记**的线段树来维护这一操作。线段树的写法会在接下来给出。 你需要构造一条从 $s$ 到 $t$ 的路径，满足达到结点 $t$ 时，其线段树上所有标记的和的最小。输出这个最小值。 以下是线段树的伪代码：（为了方便选手阅读，题目附件中给出了线段树的 C++ 源代码） $$ \begin{array}{l}\hline\hline\\[-0.8em] \textbf{Algorithm: }\text{SegTree}\\\hline\\[-0.5em] \begin{array}{rl} 1& \mathbf{Input.} \text{ 长度为 $k$ 的 $a$ 数组，初始全为 $0$}\\ 2& \mathbf{Output.} \text{ $a$ 数组进行若干次区间加操作后得到的结果}\\ 3& \mathbf{Method.}\\ 4& \mathrm{Add}(L,R,x)\\ 5& \quad\mathrm{Add0}(L,R,x,root,1,k)\\ 6& \mathrm{Add0}(L,R,x,u,l,r)\\ 7& \quad\mathbf{if}\ L \le l\ \mathbf{and}\ r\le R\\ 8& \quad\quad \mathrm{tag}(u) \gets \mathrm{tag}(u) + x\\ 9& \quad\quad \mathbf{return}\\ 10& \quad mid \gets \lfloor\frac{l+r} 2\rfloor\\ 11& \quad \mathrm{tag}(\mathrm{lson}(u)) \gets \mathrm{tag}(\mathrm{lson}(u))+\mathrm{tag}(u)\\ 12& \quad \mathrm{tag}(\mathrm{rson}(u)) \gets \mathrm{tag}(\mathrm{rson}(u))+\mathrm{tag}(u)\\ 13& \quad \mathrm{tag}(u) \gets 0\\ 14& \quad\mathbf{if}\ L \le mid\\ 15& \quad\quad\mathrm{Add0}(L,R,x,\mathrm{lson}(u),l,mid)\\ 16& \quad\mathbf{if}\ mid < R\\ 17& \quad\quad\mathrm{Add0}(L,R,x,\mathrm{rson}(u),mid+1,r)\\ \end{array}\\\hline\hline \end{array} $$

- 第一行五个整数 $n,m,k,s,t$。 - 接下来 $m$ 行，每行五个整数 $u_i,v_i,l_i,r_i,w_i$。

- 共一行一个整数，表示沿着你构造的路径从 $s$ 到达 $t$ 后线段树上所有懒标记的权值之和。

4 4 5 1 4
1 2 1 2 2
1 3 4 5 1
2 4 2 3 1
3 4 3 5 2

5

10 19 5 6 1
2 1 1 3 592
6 8 3 5 488
10 9 4 4 548
10 4 1 4 442
6 5 1 3 422
9 7 1 4 529
5 8 1 1 559
5 9 1 5 560
5 8 2 3 434
5 9 3 3 592
4 7 2 2 594
7 9 5 5 595
4 1 4 4 501
3 9 1 2 410
10 6 2 4 509
6 10 4 5 455
2 4 2 5 444
4 3 4 5 541
8 7 1 1 463

2295

### 样例解释 #### 样例 \#1  容易发现，样例 $1$ 中有且仅有两条可能的路径：$1\to 2\to 4$ 与 $1\to 3\to 4$。下面分别计算这两条路径最终 $\text{tag}$ 的权值和。  考虑画出这棵 $k=5$ 的线段树。  走了边 $1\to 2$ 后，$[1,2]$ 节点被打上了权值为 $2$ 的 $\text{tag}$。  走了 $2\to 4$ 后，$[2,2]$ 节点和 $[3,3]$ 节点被打上了值为 $1$ 的 $\text{tag}$；但是 $[1,2]$ 节点的标记进行了下推（因为使 $[2,3]$ 区间 $+1$ 的时候会访问到 $[1,2]$ 节点，而 $[1,2]\nsubseteq[2,3]$，故而发生标记下推），因此 $[1,1]$ 节点和 $[2,2]$ 节点的 $\text{tag}$ 分别加上了 $2$，最终成了如图所示的模样。 因此走到 $4$ 之后所有结点的 $\text{tag}$ 之和为 $2+3+1=6$。 ---  对于另外一条路径，首先对 $[4,5]$ 加上 $1$。  接着对 $[3,5]$ 加上 $2$。未发生带有 $\text{tag}$ 的节点的标记下推，因此最终的权值为 $2+3=5$。 由于 $6>5$，因而最终的答案为 $5$。 ### 数据范围及约定 $$ \def\arraystretch{1.5} \begin{array}{|c|c|c|c|c|c|c|}\hline \textbf{subtask}& \textbf{分值}& {\bm n\le} & {\bm m\le} & {\bm k\le} & \textbf{特殊性质} & \textbf{subtask 依赖}\cr\hline 1 & 10& 10 & 30 & 5 & - & -\cr\hline 2 & 5&30 & 30 & 12 & \textbf{AB} &-\cr\hline 3 & 20&30 & 500 & 12 & \textbf{B} &2 \cr\hline 4 & 15&200 & 3\times 10^3 & 25 & \textbf{B}&3\cr\hline 5 & 50&200 & 3\times 10^3 & 25 & - &4\cr\hline \end{array} $$ - **特殊性质** $\textbf{A}$：保证有且仅有一条从 $s$ 到 $t$ 的路径。 - **特殊性质** $\textbf{B}$：保证图中不存在环。 对于 $100\%$ 的数据，有 $1 \le s,t,u_i,v_i \leq n \leq 200$，$1 \leq m \leq 3\times 10^3$，$1 \leq l_i\le r_i \leq k \leq 25$，$1 \leq w_i \leq 10^3$。 ### 提示 在附件中有两个版本的线段树。$\text{Lite}$ 版本**仅**包含了在本题中你会用到的下推标记的操作，而标准版则较为完整地支持区间加、区间求和。选手可根据自己的喜好使用。