UOJ Logo LFYZ Online Judge

LFYZOJ

#343. 【2018 国庆雅礼 NOIP 培训】D4T2 y

统计

问题背景

$\dfrac 1 4$ 遇到了一道水题,叕完全不会做,于是去请教小 D。小 D 懒得理 $\dfrac 1 4$,直接就离开了。于是,$\dfrac 1 4$ 只好来问你,

这道题是这样的:

问题描述

给定一个无向图,$n$ 个点(从 1 开始编号)、$m$ 条边(长度为 1),每条边有一个权值 $c(c \in \{0, 1\})$。

一条路径,可以表示为一个长度为经过边数的 01 串,串的第 $i$ 位为经过的第 $i$ 条边的权值。

两条路径相同,当且仅当表示其的 01 串相同。

求从 1 号点出发、长度为 $d$ 的路径种数。

输入格式

第一行,三个整数,$n, m, d$。

接下来 $m$ 行,每行三个整数 $u, v, c$,代表一条边连接 $u$ 和 $v$,权值为 $c$。

输出格式

输出一行,一个整数,代表答案。

样例

Input

3 2 3
1 2 0
1 3 1

Output

4

Explanation

$$ 1 \rightarrow 2 \rightarrow 1 \rightarrow 2 \Rightarrow 000, 1 \rightarrow 2 \rightarrow 1 \rightarrow 3 \Rightarrow 001, 1 \rightarrow 3 \rightarrow 1 \rightarrow 2 \Rightarrow 110, 1 \rightarrow 3 \rightarrow 1 \rightarrow 3 \Rightarrow 111 $$

子任务

保证 $n \in [1, 90],m \in [0, n (n - 1)],d \in [1, 20],u, v \in [1, n],c \in \{0, 1\}$。

Subtask    分值    $n\le$    $d\le$    其他限制
121304
2397013
3129020保证 $c\in\{0\}$
4930
51990

时限 1s,空限 512M

来源

2018 国庆雅礼 NOIP 培训。一切权利归原作者所有。侵权删除。