#P1987. Distance Statistics
Distance Statistics
描述
农夫约翰对需要回答大量距离查询感到沮丧,因此他决定提出一种可以让他获取更多信息的查询。具体来说,他会提供一个整数,并希望知道有多少对农场之间的距离不超过 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 二月赛