UOJ Logo

NOI.AC

1S 512MB

#1516. 最小瓶颈路 加强版

Statistics

题目描述

给定一个 $n$ 个点 $m$ 条边的无向连通图,编号为 $1$ 到 $n$ ,没有自环,可能有重边,每一条边有一个正权值 $w$ 。 给出 $q$ 个询问,每次给出两个不同的点 $u$ 和 $v$ ,求一条从 $u$ 到 $v$ 的路径上边权的最大值最小是多少。

输入格式

输入第一行两个整数 $n, m$。 接下来 $m$ 行,每行三个整数 $a_i,b_i,w_i(a_i\neq b_i)$,表示一条边 $(a_i,b_i)$,边权为 $w_i$。 接下来一行一个整数 $q$,表示询问数量。 接下来一行四个整数 $A,B,C,P$,表示询问的生成方式。 由于本题数据规模较大,直接输入输出会占用比计算多数倍的时间,因此对询问的输入输出进行了压缩。 输入压缩方法是:读入4个整数 $A,B,C,P$,每次询问调用以下函数生成 $u$ 和 $v$: int A,B,C,P; inline int rnd(){return A=(A*B+C)%P;} 每次询问时的调用方法为: u=rnd()%n+1,v=rnd()%n+1; 若u和v相等则答案为0。 数据保证 $0\leq A

输出格式

输出共一行一个整数,表示所有询问的答案之和模 $1000000007$ 的值。 由于本题数据规模较大,直接输入输出会占用比计算多数倍的时间,因此对询问的输入输出进行了压缩。 输出压缩方法是:输出所有询问的答案之和模 $1000000007$ 的值。

样例

样例输入

样例输入

5 7
1 2 8
2 3 9
3 1 2
3 4 7
1 4 4
3 5 6
1 4 9
10
233 17 66666 19260817

样例输出

样例输出

32

数据范围与提示

对于所有数据,$n\leq 70000$,$m\leq 100000$,$q\leq 10^7$。 图片题目和数据复制自寻找 LCR。