UOJ Logo Universal Online Judge

UOJ

#551. 【UNR #4】校园闲逛

附件下载 统计

为了出题,出题人 03 喜欢在校园里闲逛。

校园可以看成抽象成是一张 $n$ 个点 $m$ 条边的有向图,第 $i$ 条边从 $a_i$ 连向 $b_i$,边权为 $c_i$。

出题人 03 总共会闲逛 $Q$ 天,在第 $i$ 天,他会从 $x_i$ 出发,到达 $y_i$,同时希望自己走过的路径边权和恰好为 $v_i$。

出题人 03 很好奇,每一天他可以有多少种不同的路径呢? 由于答案很大,你只需要回答答案对 $998244353$ 取模的结果。

同一条路径可以多次经过同一条边。两条路径相同当且仅当两条路径上的边数相同且边的编号依次相等。

输入格式

第一行四个整数 $n,m,Q,\max_v$。

接下来 $m$ 行,每行三个正整数表示 $a_i,b_i,c_i$。

接下来 $Q$ 行,每行三个正整数表示 $x_i,y_i,v_i$。

输出格式

$Q$ 行,第 $i$ 行一个整数表示第 $i$ 次询问的答案对 $998244353$ 取模的结果。

样例一

input

3 10 5 10
1 2 1
2 3 3
3 1 7
2 3 5
1 1 4
3 1 2
2 1 1
3 2 3
1 2 2
1 3 4
1 3 6
1 3 7
1 3 8
1 3 9
1 3 10

output

3
4
6
8
19

explanation

在第一天中,存在如下三条闲逛路径:($\#i$ 表示输入数据中第 $i$ 条边)

$1\ \xrightarrow{\#1}\ 2\ \xrightarrow{\#4}\ 3$

$1\ \xrightarrow{\#1}\ 2\ \xrightarrow{\#7}\ 1 \xrightarrow{\#1}\ 2\ \xrightarrow{\#2}\ 3$

$1\ \xrightarrow{\#1}\ 2\ \xrightarrow{\#7}\ 1\ \xrightarrow{\#10}\ 3$

注意一条路径可以重复经过一个点,也可以重复经过一条边。

样例二

见附加文件。

该测试点$n=3$,其余范围同测试点$1$。

数据范围

测试点编号$n=$特殊性质
$1$$8$$m \le 2000, \max_v \le 200$
$2$$1$
$3$$2$
$4$$3$
$5$$5$$x_i=1$
$6$
$7$$6$
$8$$7$
$9$$8$$x_i=1$
$10$

对于所有测试点,满足 $1 \le n \le 8,0 \le m \le 300000,1 \le \max_v \le 65000,0 \le Q \le 10000$。

对于所有测试点,满足 $1 \le a_i,b_i,x_i,y_i \le n,1 \le c_i,v_i \le \max_v$。

请注意选手程序自身常数因子对程序运行时间带来的影响

时间限制:$4\texttt{s}$

空间限制:$512\texttt{MB}$

下载

样例数据下载