OpenJudge

11:DAG上的2点简单路径的数量

总时间限制:
1000ms
内存限制:
65536kB
描述

给定有向无环图G(V,E),以及图中2个结点s和t,求s到t之间简单路径的数量。

* 如果路径中结点/边都不重复出现,则称为简单路径。

输入
第一行包含四个整数N、M、s、t,表示该图共有N个结点和M条有向边(N <= 5000,M <= 200000)。以及起点s、终点t的结点标号。
接下来M行,每行包含2个整数{u,v},表示有一条有向边 u指向v
输出
一个整数,表示s到t简单路径的数量。
* 若s无法到达t,请输出“No Path!”。
样例输入
5 8 1 5
1 2
1 4
1 5
2 5
2 3
3 4
3 5
4 5
样例输出
5
提示
* 结果保证在long long范围内
全局题号
15376
添加于
2017-07-01
提交次数
3
尝试人数
3
通过人数
2