1505：【例 2】双调路径

题目描述

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

路径是连续经过的道路组成的。总时间是各条道路旅行时间的和，总费用是各条道路所支付费用的总和。一条路径越快，或者费用越低，该路径就越好。严格地说，如果一条路径比别的路径更快，而且不需要支付更多费用，它就比较好。反过来也如此理解。如果没有一条路径比某路径更好，则该路径被称为最小路径。

这样的最小的路径有可能不止一条，或者根本不存在路径。

问题：读入网络，计算最小路径的总数。费用时间都相同的两条最小路径只算作一条。你只要输出不同种类的最小路径数即可。

输入格式

第一行有四个整数，城市总数 $n$，道路总数 $m$，起点 $s$ 和终点 $e$；

接下来的 $m$ 行每行描述了一条道路的信息，包括四个整数，两个端点 $p, r$，费用 $c$，以及时间 $t$；

两个城市之间可能有多条路径连接。

输出格式

输出一个整数，表示最小路径的总数。

样例

样例输入 #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

• 城市数 $n=4$，道路数 $m=5$，起点 $s=1$，终点 $e=4$。

• 道路信息：

  1. $2 \leftrightarrow 1$（双向），费用 $2$，时间 $1$
  2. $3 \leftrightarrow 4$（双向），费用 $3$，时间 $1$
  3. $2 \leftrightarrow 3$（双向），费用 $1$，时间 $2$
  4. $3 \leftrightarrow 1$（双向），费用 $1$，时间 $4$
  5. $2 \leftrightarrow 4$（双向），费用 $2$，时间 $4$

• 从 $1$ 到 $4$ 的可能路径：

  1. $1→2→4$：费用 $2+2=4$，时间 $1+4=5$
  2. $1→3→4$：费用 $1+3=4$，时间 $4+1=5$
  3. $1→2→3→4$：费用 $2+1+3=6$，时间 $1+2+1=4$
  4. $1→3→2→4$：费用 $1+1+2=4$，时间 $4+2+4=10$

• 最小路径的定义：没有其他路径在 费用和时间两个维度都严格优于 它。

  • 比较路径：

    • 路径 $1$ 和 $2$：费用 $4$，时间 $5$
    • 路径 $3$：费用 $6$，时间 $4$
    • 路径 $4$：费用 $4$，时间 $10$

  • 路径 $4$ 比路径 $1$ 和 $2$ 差（时间更长，费用相同），比路径 $3$ 差（费用相同但时间更长）。

  • 路径 $1$ 和 $2$ 与路径 $3$ 无法比较：路径 $3$ 时间更短但费用更高，路径 $1$ 和 $2$ 费用更低但时间更长。

  • 因此最小路径有 $2$ 类：

    1. 费用 $4$，时间 $5$（包含路径 $1$ 和 $2$，但费用时间相同，只算一种）
    2. 费用 $6$，时间 $4$（路径 $3$）

  • 输出 $2$。

数据范围

• $1 \le n \le 100$
• $0 \le m \le 300$
• $1 \le s, e, p, r \le n$
• $0 \le c, t \le 100$
• 保证 $s \ne e$，$p \ne r$

时空限制

• 时间限制：1000 ms
• 内存限制：65536 KB

注意：本题是双权值最短路径问题，需要找到所有 Pareto 最优解（非支配解）。可以使用动态规划或搜索，状态设计为 dp[u][cost] 表示到达节点 $u$ 且总费用为 $cost$ 时的最小时间，然后统计所有 Pareto 最优的 (cost, time) 对。由于费用和时间的范围较小（$\le 100 \times 300 = 30000$），状态数可行。