TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3328
  • 题目
  • P3328 [Usaco2004 Feb]距离状态
    限制 : 时间限制 : 20000 MS   空间限制 : 65536 KB
    问题描述

     农夫约翰有N(2≤N≤40000)个农场,标号1到N,M(2≤M≤40000)条的不同的垂直或水
    平的道路连结着农场,道路的长度不超过1000.这些农场的分布就像下面的地图一样,

    图中农场用F1..F7表示, 每个农场最多能在东西南北四个方向连结4个不同的农场.此外,农场只处在道路的两端.道路不会交叉且每对农场间有且仅有一条路径.
     

    约翰提供了一个整数K(1≤K≤10^9),希望你输出有多少对农场之间的距离是不超过K的.

    输入格式

    第1行:两个分开的整数N和M.
    第2到M+1行:每行包括4个分开的内容,F1,F2,三,D分别描述两个农场的编号,道路的长度,F1到F2的方向N,E,S,W
    第M+2行:一个整数K.

    输出格式

     农场之间的距离不超过K的对数.

    样例输入

    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

    样例输出

    5

    提示

    样例说明:
    有五对道路之间的距离小于10
    1-4,距离为3
    4-7,距离为2
    1-7,距离为5
    3-5,距离为7
    3-6,距离为9


    来源  USACO 2004 February poj1987