TouchStone
  Please Login
Login Sign Up
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P3328
  • Problem
  • P3328 [Usaco2004 Feb]距离状态
    Limits : Time Limit : 20000 MS   Memory Limit : 65536 KB
    Description

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

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

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

    Input Format

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

    Output Format

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

    Sample Input

    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

    Sample Output

    5

    Hint

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


    Source  USACO 2004 February poj1987