[湖北省选模拟 2024] 时与风 / wind

风带来故事的种子，时间使之神话。

你在 $N$ 个锚点间，沿着 $M$ 条有向航道，使用风之翼进行飞行。锚点依次编号为 $1,2,\cdots,N$，有向航道依次编号为 $1,2,\cdots,M$。第 $i$ 条航道的出发锚点为 $u_i$，到达锚点为 $v_i$。 由于巴巴斯托与时间存在神秘的联系，第 $i$ 条航道将在时刻 $O_i$ 开启，在时刻 $C_i$ **后**关闭。**也就是说，对于任意的 $O_i \le t \le C_i$，你可以在时刻 $t$ 由锚点 $u_i$ 进入航道 $i$。**进入航道后，空间上，你将直接到达锚点 $v_i$，时间上，时间将**等概率**的变化为 $[L_i,R_i]$ 中的一个实数对应的时刻。**注意到达一个锚点后，你必须在同一时刻立刻进入下一段航道，否则你必须在此结束飞行。** 你将从锚点 $S$ 出发，尝试访问锚点 $i(1\le i\le N)$，你需要对于锚点 $i$ 确定一条路径 $E_1,E_2,E_3,\cdots,E_k$，其中 $E_x(1\le x\le k)$ 表示一条航道。要求 $E_1$ 从锚点 $S$ 出发，$E_k$ 到达锚点 $i$，且对于 $1\le j<k$，满足 $E_j$ 的到达锚点与 $E_{j+1}$ 的出发锚点相同。一条路径是**稳定路径**，当且仅当无论每次通过航道后时间如何变化，都可以走完整条路径。一条**稳定路径的到达时间**是通过路径前往锚点 $i$ 时，**最晚的**可能到达锚点 $i$ 的时刻。访问**锚点 $i$ 的稳定到达时间 $T_i(i \neq S)$** 是所有到达 $i$ 的稳定路径中到达时间的**最小值**。你可以在任意非负时刻出发。**如果不存在访问锚点 $i$ 的稳定路径或 $i=S$，则 $T_i=0$。** 请你求出 $T_i(1\le i\le N)$ 的最大值。

输入共 $M+1$ 行。 输入的第一行为三个整数 $N,M,S$，分别表示锚点数、航道数和起点锚点。 接下来 $M$ 行，每行包含六个整数 $u_i,v_i,O_i,C_i,L_i,R_i$，描述了第 $i$ 条航道的有关信息，变量具体含义见题目描述部分。

输出一行一个整数，表示 $T_i$ 的最大值。

4 10 1
4 2 6 20111 6 11900
2 4 2 10786 13 23576
2 1 3 5274 16 13903
2 1 2 17162 1 26120
1 2 1 42040 11 16065
2 1 4 23690 18 26541
2 3 9 18977 2 26795
4 1 4 51880 1 25060
1 4 13 17776 3 28236
1 4 1 19112 1 10131

26795

见选手目录下的 wind/wind2.in 与 wind/wind2.ans。

见选手目录下的 wind/wind3.in 与 wind/wind3.ans。

见选手目录下的 wind/wind4.in 与 wind/wind4.ans。

### 样例解释 1 对于锚点 $1$，显然有 $T_1=0$。 对于锚点 $2$，沿路径 $1 \rightarrow 2$ ，$T_2=16065$。 对于锚点 $3$，沿路径 $1 \rightarrow 2 \rightarrow 3$ ，$T_3=26795$。 对于锚点 $4$，沿路径 $1 \rightarrow 4$ ，$T_4 = 10131$。 综上所述，答案 $\max T_i=T_3=26795$。 ### 子任务 对于所有测试数据，保证 $1 \le N,M \le 5\times 10^5$，$1 \le O_i,L_i \le 20$，$1 \le O_i \le C_i \le 10^9$，$1 \le L_i \le R_i \le 10^9$，$1\le S \le N$。 | 测试点编号 | $N\le$ | $M\le$ | $C_i,R_i\le$ | 特殊性质 | |:--:|:--:|:--:|:--:|:--:| | $1\sim 4$ | $20$ | $20$ | $10^9$ | 无 | | $5\sim 8$ | $10^5$ | $10^3$ | $10^9$| 无 | | $9\sim 10$ | $5\times 10^5$ | $5\times 10^5$ | $10^9$ | A | | $11\sim 12$ | $10^5$ | $10^5$ | $20$ | 无 | | $13\sim 14$ | $5\times 10^5$ | $5\times 10^5$ | $10^3$ | 无 | | $15\sim 20$ | $5\times 10^5$ | $5\times 10^5$ | $10^9$ | 无 | 特殊性质 A：一个锚点连接的航道数不超过 $100$。