{"problem":{"name":"[湖北省选模拟 2024] 时与风 / wind","description":{"content":"你在 $N$ 个锚点间，沿着 $M$ 条有向航道，使用风之翼进行飞行。锚点依次编号为 $1,2,\\cdots,N$，有向航道依次编号为 $1,2,\\cdots,M$。第 $i$ 条航道的出发锚点为 $u_i$，到达锚点为 $v_i$。 由于巴巴斯托与时间存在神秘的联系，第 $i$ 条航道将在时刻 $O_i$ 开启，在时刻 $C_i$ **后**关闭。**也就是说，对于任意的 $O_i \\le t","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1500,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10199"},"statements":[{"statement_type":"Markdown","content":"你在 $N$ 个锚点间，沿着 $M$ 条有向航道，使用风之翼进行飞行。锚点依次编号为 $1,2,\\cdots,N$，有向航道依次编号为 $1,2,\\cdots,M$。第 $i$ 条航道的出发锚点为 $u_i$，到达锚点为 $v_i$。\n\n由于巴巴斯托与时间存在神秘的联系，第 $i$ 条航道将在时刻 $O_i$ 开启，在时刻 $C_i$ **后**关闭。**也就是说，对于任意的 $O_i \\le t \\le C_i$，你可以在时刻 $t$ 由锚点 $u_i$ 进入航道 $i$。**进入航道后，空间上，你将直接到达锚点 $v_i$，时间上，时间将**等概率**的变化为 $[L_i,R_i]$ 中的一个实数对应的时刻。**注意到达一个锚点后，你必须在同一时刻立刻进入下一段航道，否则你必须在此结束飞行。**\n\n你将从锚点 $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$。**\n\n请你求出 $T_i(1\\le i\\le N)$ 的最大值。\n\n## Input\n\n输入共 $M+1$ 行。\n\n输入的第一行为三个整数 $N,M,S$，分别表示锚点数、航道数和起点锚点。\n\n接下来 $M$ 行，每行包含六个整数 $u_i,v_i,O_i,C_i,L_i,R_i$，描述了第 $i$ 条航道的有关信息，变量具体含义见题目描述部分。\n\n## Output\n\n输出一行一个整数，表示 $T_i$ 的最大值。\n\n[samples]\n\n## Background\n\n风带来故事的种子，时间使之神话。\n\n## Note\n\n### 样例解释 1\n\n对于锚点 $1$，显然有 $T_1=0$。\n\n对于锚点 $2$，沿路径 $1 \\rightarrow 2$ ，$T_2=16065$。\n\n对于锚点 $3$，沿路径 $1 \\rightarrow 2 \\rightarrow 3$ ，$T_3=26795$。\n\n对于锚点 $4$，沿路径 $1 \\rightarrow 4$ ，$T_4 = 10131$。\n\n综上所述，答案 $\\max T_i=T_3=26795$。\n\n### 子任务\n\n对于所有测试数据，保证 $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\n| 测试点编号 | $N\\le$ | $M\\le$ | $C_i,R_i\\le$ | 特殊性质 |\n|:--:|:--:|:--:|:--:|:--:|\n| $1\\sim 4$ | $20$ | $20$ | $10^9$ | 无 |\n| $5\\sim 8$ | $10^5$ | $10^3$ | $10^9$| 无 |\n| $9\\sim 10$ | $5\\times 10^5$ | $5\\times 10^5$ | $10^9$ | A |\n| $11\\sim 12$ | $10^5$ | $10^5$ | $20$ | 无 |\n| $13\\sim 14$ | $5\\times 10^5$ | $5\\times 10^5$ | $10^3$ | 无 |\n| $15\\sim 20$ | $5\\times 10^5$ | $5\\times 10^5$ | $10^9$ | 无 |\n\n特殊性质 A：一个锚点连接的航道数不超过 $100$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10199","tags":["2024","O2优化","湖北"],"sample_group":[["4 10 1\n4 2 6 20111 6 11900\n2 4 2 10786 13 23576\n2 1 3 5274 16 13903\n2 1 2 17162 1 26120\n1 2 1 42040 11 16065\n2 1 4 23690 18 26541\n2 3 9 18977 2 26795\n4 1 4 51880 1 25060\n1 4 13 17776 3 28236\n1 4 1 19112 1 10131","26795"],["见选手目录下的 wind/wind2.in 与 wind/wind2.ans。",""],["见选手目录下的 wind/wind3.in 与 wind/wind3.ans。",""],["见选手目录下的 wind/wind4.in 与 wind/wind4.ans。",""]],"created_at":"2026-03-03 11:09:25"}}