#1375. [Baltic2002]Bicriterial routing 双调路径

内存限制:64 MiB 时间限制:5 Sec

题目描述

来越多,因此选择最佳路径是很现实的问题。城市的道路是双向的,每条道路有固定的旅行时间以及需要支付的费用。路径由连续的道路组成。总时间是各条道路旅行时间的和,总费用是各条道路所支付费用的总和。同样的出发地和目的地,如果路径A比路径B所需时间少且费用低,那么我们说路径A比路径B好。对于某条路径,如果没有其他路径比它好,那么该路径被称为最优双调路径。这样的路径可能不止一条,或者说根本不存在。 给出城市交通网的描述信息,起始点和终点城市,求最优双条路径的条数。城市不超过100个,边数不超过300,每条边上的费用和时间都不超过100。

输入格式

第一行给出有多少个点,多少条边,开始点及结束点. 下面的数据用于描述这个地图

输出格式

有多少条最优双调路径

样例

样例输入


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

样例输出


			
2

数据范围与提示