Bicriterial routing 双调路径

题目描述:

如今的道路收费发展很快，道路的密度越来越大，因此选择最佳路径是很现实的问题。城市的道路是双向的，每条道路有固定的旅行时间以及需要支付的费用。

路径由连续的道路组成。总时间是各条道路旅行时间的和，总费用是各条道路所支付费用的总和。同样的出发地和目的地，如果路径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

时间限制: 1000ms
空间限制: 256MB

---

来源: Baltic2002