#417. 双调路径

双调路径

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

原题来自:BalticOI 2002

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

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

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

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

输入格式

第一行有四个整数,城市总数 n\red{n},道路总数 m\red{m},起点和终点城市 s,e\red{s,e}

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

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

输出格式

仅一个数,表示最小路径的总数。

样例

输入样例

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

样例输入如下图:

img

1\red{1}4\red{4 }4\red{4 }条路径。为 124\red{1→2→4}(费用为 4\red{4},时间为 5\red{5}),134\red{1→3→4}(费用为 4\red{4},时间为 5\red{5}),1234\red{1→2→3→4}(费用为 6\red{6},时间为 4\red{4}),1324\red{1→3→2→4}(费用为 4\red{4},时间为 10\red{10})。

134\red{1→3→4}124\red{1→2→4}1324\red{1→3→2→4} 更好。有两种最佳路径:费用为 4\red{4},时间为 5124\red{5(1→2→4}134\red{1→3→4)}和 费用为 6\red{6},时间为 41234\red{4(1→2→3→4)}

提示

对于全部数据,1n100,0m300,1s,e,p,rn,0c,t100\red{1≤n≤100,0≤m≤300,1≤s,e,p,r≤n,0≤c,t≤100},保证 se,pr\red{s\not =e,p\not =r}

中心团队spfa优化

未参加
状态
已结束
规则
IOI
题目
4
开始于
2023-12-9 15:07
结束于
2023-12-19 15:07
持续时间
240 小时
主持人
参赛人数
33