/
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
ある国には N 個の都市があり、それぞれ 1 から N の番号が付けられています。各都市には代表者が 1 人ずついて、都市 i の代表者を 代表者 i と呼びます。代表者 i と都市 i は一対一に対応しています。
この国には M 本の道路があり、各道路は双方向に通行できます。k 番目(1 \leq k \leq M)の道路は都市 U_k と都市 V_k を結び、通過にかかる時間は W_k です。同じ都市の組を結ぶ道路は高々 1 本であり、ある都市からそれ自身への道路(自己ループ)は存在しません。また、すべての都市の組が道路で行き来できるとは限りません(グラフは連結であるとは限りません)。
異なる 2 つの都市 i, j(i \neq j)について、都市 i から都市 j への最短移動時間を d(i, j) と定めます。道路をたどって都市 i から都市 j へ到達できない場合は d(i, j) = \infty とします。道路の辺重みはすべて正であるため最短移動時間は常に well-defined であり、道路は双方向に通行できるので、つねに d(i, j) = d(j, i) が成り立ちます。
各代表者 i には忍耐力 S_i(正整数)が定められています。代表者 i は、自分以外の都市 j(j \neq i)について、最短移動時間 d(i, j) が忍耐力 S_i 以下であるとき、都市 j に対して 不満を抱かない ものとします。逆に d(i, j) > S_i であるとき、都市 j に対して 不満を抱く ものとします。S_i は有限の正整数であるため、到達できない都市(d(i,j) = \infty)に対しては必ず不満を抱くことに注意してください。
代表者 i の 不満の個数 C_i を次のように定義します:
C_i = |\{ \, j \mid j \neq i, \; d(i, j) > S_i \, \}|
すなわち、C_i は代表者 i が不満を抱く都市の個数です。
高橋君はこの国の調査を行っており、各代表者の不満の個数をもとに、次のような分析をしたいと考えました。
異なる 2 人の代表者の組 (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\} を結ぶ道路は高々 1 本である
- 入力はすべて整数である
入力
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
- 1 行目には、都市の数 N と道路の本数 M がスペース区切りで与えられる。
- 2 行目には、各代表者の忍耐力 S_1, S_2, \ldots, S_N がスペース区切りで与えられる。
- 続く M 行のうち k 行目(1 \leq k \leq M)には、k 番目の道路が結ぶ 2 つの都市の番号 U_k, V_k と通過にかかる時間 W_k がスペース区切りで与えられる。
出力
友好ペアの総数を 1 行で出力せよ。
入力例 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
Score : 400 pts
Problem Statement
A country has N cities, numbered from 1 to N. Each city has exactly one representative, and the representative of city i is called representative i. Representative i and city i are in one-to-one correspondence.
The country has M roads, each of which can be traversed in both directions. The k-th road (1 \leq k \leq M) connects city U_k and city V_k, and takes time W_k to traverse. There is at most one road connecting any pair of cities, and there are no roads from a city to itself (no self-loops). Furthermore, it is not guaranteed that all pairs of cities can reach each other via roads (the graph is not necessarily connected).
For two distinct cities i, j (i \neq j), let d(i, j) denote the shortest travel time from city i to city j. If city j cannot be reached from city i by following roads, then d(i, j) = \infty. Since all edge weights are positive, the shortest travel time is always well-defined, and since roads can be traversed in both directions, d(i, j) = d(j, i) always holds.
Each representative i has a patience value S_i (a positive integer). Representative i is not dissatisfied with city j (j \neq i) if the shortest travel time d(i, j) is at most their patience S_i. Conversely, if d(i, j) > S_i, representative i is dissatisfied with city j. Note that since S_i is a finite positive integer, a representative is always dissatisfied with any unreachable city (where d(i,j) = \infty).
The dissatisfaction count C_i of representative i is defined as follows:
C_i = |\{ \, j \mid j \neq i, \; d(i, j) > S_i \, \}|
In other words, C_i is the number of cities that representative i is dissatisfied with.
Takahashi is conducting a survey of this country and wants to perform the following analysis based on each representative's dissatisfaction count.
A pair of two distinct representatives (i, j) (i < j) is called a friendly pair if it satisfies all of the following conditions:
- d(i, j) \leq S_i and d(i, j) \leq S_j (that is, representative i is not dissatisfied with city j, and representative j is not dissatisfied with city i)
- C_i = C_j (their dissatisfaction counts are equal)
Find and output the total number of friendly pairs.
Constraints
- 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)
- There is at most one road connecting the same pair of cities \{U_k, V_k\}
- All input values are integers
Input
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
- The first line contains the number of cities N and the number of roads M, separated by a space.
- The second line contains the patience values S_1, S_2, \ldots, S_N of each representative, separated by spaces.
- The following M lines each contain, for the k-th road (1 \leq k \leq M), the two city numbers U_k, V_k connected by the road and the travel time W_k, separated by spaces.
Output
Output the total number of friendly pairs in a single line.
Sample Input 1
4 4 3 3 3 3 1 2 1 2 3 1 3 4 1 1 3 2
Sample Output 1
6
Sample Input 2
2 0 1 1
Sample Output 2
0
Sample Input 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
Sample Output 3
3
Sample Input 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
Sample Output 4
6
Sample Input 5
1 0 1000000000
Sample Output 5
0