← 返回题目列表

AtCoder · awc0067_d

D. 城市网络

中文机器翻译题面 查看原题

分数: 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