分数: 400 分
问题陈述
一个国家有 N 城市,编号自 1 to N。每个城市只有一名代表,城市的代表 i 被称为 代表 i。代表 i 和城市 i 一一对应。
国家有 M 道路,每条道路都可以双向行驶。的 k第路(1 \leq k \leq M) 连接城市 U_k 和城市 V_k,并且需要时间 W_k 进行遍历。任意一对城市之间至多有一条道路连接,并且不存在从城市到其自身的道路(无自环路)。此外,不保证所有城市对都可以通过道路相互到达(图表不一定是连通的)。
对于两个不同的城市 i, j (i \neq j),让 d(i, j) 表示从城市出发的最短行程时间 i 前往城市 j。如果城市 从城市无法到达 j 从城市无法到达 i 沿着道路行驶,然后 d(i, j) = \infty。由于所有边权重均为正,因此最短行驶时间始终是明确定义的,并且由于道路可以在两个方向上穿越, d(i, j) = d(j, i) 始终成立。
各代表 i 有耐心值 S_i (正整数)。代表 i is 不满意 与城市 j (j \neq i) 如果最短行程时间 d(i, j) 最多就是他们的耐心 S_i。相反,如果 d(i, j) > S_i,代表 i is 不满意 与城市 j。请注意,自从 S_i 是一个有限正整数,代表总是对任何无法到达的城市不满意(其中 d(i,j) = \infty).
的 不满意计数 代表 C_i 代表的 i 定义如下:
C_i = |\{ \, j \mid j \neq i, \; d(i, j) > S_i \, \}|
换句话说, C_i 是代表的城市数量 i 不满意。
高桥正在对这个国家进行一项调查,并希望根据每个代表的不满程度进行以下分析。
一对两个不同的代表 (i, j) (i < j) 被称为 友好的一对 如果满足以下所有条件:
- d(i, j) \leq S_i 和 d(i, j) \leq S_j (即代表 i 对城市没有不满意 j,以及代表 j 对城市没有不满意 i)
- C_i = C_j (他们的不满数量相等)
查找并输出友好对的总数。
约束
- 1 \leq N \leq 400
- 0 \leq M \leq \frac{N(N-1)}{2}
- 1 \leq S_i \leq 10^9 (1 \leq i \leq N)
- 1 \leq U_k, V_k \leq N (1 \leq k \leq M)
- U_k \neq V_k (1 \leq k \leq M)
- 1 \leq W_k \leq 10^9 (1 \leq k \leq M)
- 最多有一条道路连接同一对城市 \{U_k, V_k\}
- 所有输入值均为整数
输入
N M S_1 S_2 \ldots S_N U_1 V_1 W_1 U_2 V_2 W_2 \vdots U_M V_M W_M
- 第一行包含城市数量 N 和道路数量 M,用空格分隔。
- 第二行包含耐心值 每个代表的 S_1, S_2, \ldots, S_N ,用空格分隔。
- 以下 M 行各包含,对于 k第路(1 \leq k \leq M), 两个城市号码 U_k, V_k 连接道路和出行时间 W_k,用空格分隔。
输出
在一行中输出友好对的总数。
示例输入 1
4 4 3 3 3 3 1 2 1 2 3 1 3 4 1 1 3 2
示例输出 1
6
示例输入 2
2 0 1 1
示例输出 2
0
示例输入 3
6 7 5 5 5 5 5 5 1 2 2 2 3 2 3 4 2 4 5 2 5 6 2 1 4 5 2 5 5
示例输出 3
3
示例输入 4
10 15 10 10 10 10 10 10 10 10 10 10 1 2 3 2 3 3 3 4 3 4 5 3 5 6 3 6 7 3 7 8 3 8 9 3 9 10 3 1 5 11 2 6 11 3 7 11 4 8 11 5 9 11 6 10 11
示例输出 4
6
示例输入 5
1 0 1000000000
示例输出 5
0