「BOI 2002」双调路径

题目描述

如今的道路收费发展很快。道路的密度越来越大,因此选择最佳路径是很现实的问题。城市的道路是双向的,每条道路有固定的旅行时间以及需要支付的费用。 路径是连续经过的道路组成的。总时间是各条道路旅行时间的和,总费用是各条道路所支付费用的总和。一条路径越快,或者费用越低,该路径就越好。严格地说,如果一条路径比别的路径更快,而且不需要支付更多费用,它就比较好。反过来也如此理解。如果没有一条路径比某路径更好,则该路径被称为最小路径。 这样的最小的路径有可能不止一条,或者根本不存在路径。 问题:读入网络,计算最小路径的总数。费用时间都相同的两条最小路径只算作一条。你只要输出不同种类的最小路径数即可。

输入输出格式

输入格式


第一行有四个整数,城市总数 $n$,道路总数 $m$,起点和终点城市 $s,e$。 $\newline$ 接下来的 $m$ 行每行描述了一条道路的信息:两个端点 $p,r$,费用 $c$,以及时间 $t$; $\newline$ 两个城市之间可能有多条路径连接。

输出格式


输出一行一个数,表示最小路径的总数。

输入输出样例

输入样例 #1

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

输出样例 #1

2

说明

**数据范围:** - $1\leq{n}\leq100$,$0\leq{m}\leq300$。 - $1\leq{s,e,p,r}\leq{n}$,$0\leq{c,t}\leq100$。 - $s\neq{e},p\neq{r}$。 **样例解释:** ![样例输入](https://z3.ax1x.com/2021/09/24/4DN3xP.png) 从 $1$ 到 $4$ 有 $4$ 条路径。为 $1\rightarrow 2\rightarrow 4$(费用为 $4$,时间为 $5$),$1\rightarrow 3\rightarrow 4$(费用为 $4$,时间为 $5$),$1\rightarrow 2\rightarrow 3\rightarrow 4$(费用为 $6$,时间为 $4$),$1\rightarrow 3\rightarrow 2\rightarrow 4$(费用为 $4$,时间为 $10$)。 $1\rightarrow 3\rightarrow 4$ 和 $1\rightarrow 2\rightarrow 4$ 比 $1\rightarrow 3\rightarrow 2\rightarrow 4$ 更好。有两种最佳路径:费用为 $4$,时间为 $5$($1\rightarrow 2\rightarrow 4$ 和 $1\rightarrow 3\rightarrow 4$)和 费用为 $6$,时间为 $4$($1\rightarrow 2\rightarrow 3\rightarrow 4$)。