4490 - 第十课:最短路径计数问题

给定一个有向图,顶点从1到n编号。
给定起点s和终点t,求出s到t的最短路径数目以及比最短路长度刚好大1的数目之和。
如下图所示,从1到5最短路为1 → 2 → 5 以及 1 → 3 → 5,长度为6。1 → 3 → 4 → 5长度为7。
 

输入

第一行输入两个整数$ n(2 \le n \le 10^3), m(1 \le m \le 10^4) $。
接下来m行,每行输入三个整数$ a_i, b_i(1 \le a_i, b_i \le n, a_i \ne b_i), w_i(1 \le w_i \le 10^3) $,表示$ a_i $到$ b_i $有一条长度为$ w_i $的有向边。
最后输入两个整数$ s,t (1 \le s, t \le n, s \ne t) $。
输入保证s到t可达。

输出

输出一个整数表示答案。

答案不超过$ 10^9 $。

样例

输入

5 8
1 2 3
1 3 2
1 4 5
2 3 1
2 5 3
3 4 2
3 5 4
4 5 3
1 5

输出

3
时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题