#P1987. Distance Statistics

Distance Statistics

描述

农夫约翰对需要回答大量距离查询感到沮丧,因此他决定提出一种可以让他获取更多信息的查询。具体来说,他会提供一个整数K1K1,000,000,000 K(1 ≤ K ≤ 1,000,000,000),并希望知道有多少对农场之间的距离不超过 K(距离是指从一个农场到另一个农场所需的道路长度之和)。请只计算不同的农场对(即不要计算像 (农场 #5, 农场 #5) 这样的对)。

输入

  • 第 1 行到第 M+1 行:与“导航噩梦”("Navigation Nightmare")的输入格式相同。
  • 第 M+2 行:一个单独的整数 K。

输出

  • 第 1 行:距离不超过 K 的农场对的数量。

输入数据 1

7 6
1 6 13 E
6 3 9 E
3 5 7 S
4 1 3 N
2 4 20 W
4 7 2 S
10

输出数据 1

5

提示

有 5 条道路的长度小于或等于 10,分别是 1-4 (3), 4-7 (2), 1-7 (5), 3-5 (7) 和 3-6 (9)。

来源

USACO 2004 二月赛