#P12652. [集训队互测2025day2]生命的循环

    ID: 11838 传统题 2000ms 512MiB 尝试: 3 已通过: 1 难度: 10 上传者: 标签>图论数据结构强连通分量数论字符串KMP拓扑排序CF3300模运算

[集训队互测2025day2]生命的循环

题目描述

生命是一张由 nn 个神经节点与 mm 条神经构成的带权有向图,允许存在自环和重边。

第 ii 条神经记为 (ui,vi,wi)(u_i,v_i,w_i),表示一条从 uiu_i 指向 viv_i 的有向边,长度为 wiw_i。

数据保证:对于图中的任意一条简单回路,其包含的所有边权之和不超过某个定值 BB,并且始终有 B≤100B\le 100。

定义 f(u,t)f(u,t) 表示在时刻 tt,神经节点 uu 是否处于兴奋状态。

兴奋会沿神经传导:对于一条神经 (ui,vi,wi)(u_i,v_i,w_i),若节点 uiu_i 在时刻 tt 兴奋,则会向 viv_i 传递信号,使 viv_i 在时刻 t+wit+w_i 进入兴奋状态。

节点的兴奋状态不会自动保留到下一时刻。也就是说,某个节点在一个时刻进入兴奋状态后,会立刻沿所有出边继续传递信号;之后若没有其它信号在某个时刻到达该节点,则该节点在该时刻不兴奋。

如果存在边权和为 00 的简单回路,那么信号可能在同一个时刻沿该回路递归传播。此时可以把整条零权简单回路等效地看作一个节点;这种传播不会让兴奋状态自动延续到下一时刻。

初始时刻 00,只有 11 号节点受到刺激并进入兴奋状态。此后信号在整个网络中不断传播。

保证经过充分长的时间后,nn 号节点的兴奋状态会进入周期。请你求它的最小正周期 pp,即最小的正整数 pp,使得存在某个有限的非负整数 MM,满足

∀x≥M, f(n,x)=f(n,x+p)\forall x\ge M,\ f(n,x)=f(n,x+p)。

由于答案可能非常大,只需输出 p mod (109+9)p\bmod (10^9+9)。

输入格式

第一行输入三个整数 n,m,typen,m,type:

  • nn 表示神经节点数;
  • mm 表示神经条数;
  • typetype 表示当前测试点所属的子任务编号。样例中 type=0type=0。

随后 mm 行,每行三个整数 ui,vi,wiu_i,v_i,w_i,表示一条从 uiu_i 指向 viv_i、长度为 wiw_i 的神经。

type 仅用于标识子任务,解题时不需要依赖它计算答案。

输出格式

输出一行一个整数,表示最小周期 pp 对 109+910^9+9 取模后的结果。

输入输出样例

输入

5 7 0
1 2 0
2 3 1
3 2 5
3 5 1
1 4 0
4 4 9
4 5 1

输出

18

数据范围

对于所有测试数据:

  • 2≤n≤50002\le n\le 5000;
  • 0≤m≤1040\le m\le 10^4;
  • 1≤ui,vi≤n1\le u_i,v_i\le n;
  • 0≤wi≤B≤1000\le w_i\le B\le 100;
  • 任意简单回路的边权和不超过 BB。

子任务

子任务 分值 限制
1 原图为 DAG,即不存在任何简单回路
2 8 n,B≤10n,B\le 10,m≤15m\le 15
3 11 原图强连通
4 10 至少存在一条包含节点 nn 的简单回路
5 19 所有简单回路的点集两两不相交,且这些简单回路的总长度两两互质
6 9 所有简单回路的点集两两不相交,且每条简单回路的总长度都是某个质数的正整数次幂
7 18 B≤30B\le 30
8 24 无特殊限制