QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 512 MB Total points: 100
[+30]
统计

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

一条编号为 i 的神经 (ui,vi,wi) 单向地连接着两个神经节点 uivi,长度为 wi

生命的网络不会过于复杂,对于任意一条简单回路,其包含的所有神经长度之和不大于一个定值 B

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

兴奋会沿着神经传导,对于第 i 条神经 (ui,vi,wi),若神经节点 ui 在时刻 t 是兴奋的,那么其会向节点 vi 传递神经信号,使其在时刻 t+wi 进入兴奋状态。

神经节点的兴奋状态不会保留到下一个时刻,即神经节点 u 在进入兴奋状态后会沿其它神经立刻向外传递神经信号;接下来的时刻里,如果没有其它神经向它传递神经信号,则该神经节点会保持不兴奋的状态。

如果在同一个时刻,一个节点进入兴奋状态后其递归地向自身传递了神经信号,兴奋状态也不会保留到下一个时刻。(换句话说,数据中存在边权和为 0 的简单回路,此时你可以将整条简单回路等效地看作单个神经节点处理。)

生命的伊始,神秘的力量刺激了 1 号神经节点,使其在时刻 0 时进入兴奋状态。从此开始无数的时间里,生命的讯号便在神经网络中不息传递着。

在经过葛立恒数个时刻的洗礼后,一位实力强大的 OIer——你,历经千辛万苦,终于抵达了 n 号神经节点。在那里,你看到生命总是趋于循环。

即,保证经过充分长的时间后,n 号神经节点以一个固定时间周期依据一定模式重复进入兴奋状态。

现在的你开始好奇,此时 n 号神经节点的进入兴奋状态的最小周期是多少?

亦即,你需要求出一个最小的正整数 p,满足存在一个有限的非负整数 M,使得

xM,f(n,x)=f(n,x+p)

由于 p 可能很大,你只需要输出 p109+9 取模后的结果。

输入格式

第一行输入三个数 n,m,type,依次表示神经节点个数、神经条数、子任务编号。你可以通过 type 来判断 B 的取值。特别地,对于题面中的样例,type=0

接下来 m 行,第 i 行三个数 ui,vi,wi,描述第 i 条神经由神经节点 ui 指向神经节点 vi,长度为 wi

输出格式

输出一行一个正整数,表示答案 p 对于 109+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

数据约束

对于所有数据满足 2n5000, 0m104, 1ui,vin, 0wiB100

子任务

  • Subtask 1 (1 pts): 神经构成的有向图是一张 DAG,即不存在任何简单回路。
  • Subtask 2 (8 pts): n,B10,m15
  • Subtask 3 (11 pts): 原图强连通。即任意一对神经节点间都可以通过神经组成的有向路径互相可达。
  • Subtask 4 (10 pts): 存在至少一条包含点 n 的简单回路。
  • Subtask 5 (19 pts): 所有的简单回路点集互不相交,且总长度两两互质。
  • Subtask 6 (9 pts): 所有的简单回路点集互不相交,且总长度均为质数的若干次幂。
  • Subtask 7 (18 pts): B30
  • Subtask 8 (24 pts): 无特殊限制。