首页 > 试题广场 >

字符路径

[编程题]字符路径
给一个含n个点m条边的有向无环图（允许重边，点用1到n的整数表示），每条边上有一个字符，问图上有几条路径满足路径上经过的边上的字符组成的的字符串去掉空格后以大写字母开头，句号 '.' 结尾，中间都是小写字母，小写字母可以为0个。

输入描述:
第一行两个整数n,m
接下来m行，每行两个整数a,b和一个字符c，表示一条起点为a，终点为b的边，边上的字符是c
1 ≤ n, m ≤ 50000
1 ≤ a < b ≤ n
c可以是大小写字母、句号 '.' 或空格（方便起见用 '_' 表示空格）


输出描述:
输出一个整数，表示答案对232取模的结果
示例1

输入

6 11
1 2 A
1 2 _
3 4 _
2 4 B
2 3 a
2 3 _
2 4 b
4 5 .
3 5 .
2 5 .
5 6 _

输出

16
算法知识视频讲解
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

动态规划
上传者：牛客301599号
难度：
0条回答 20浏览

热门推荐

通过挑战的用户

查看代码

相关试题

字符路径

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号