거리 통계
시간 제한1초메모리 제한1024 MB
도로망과 정수 K가 주어질 때, 최단 거리가 K 이하인 서로 다른 농장 쌍의 개수를 구합니다.
문제
FJ는 소 마라톤 경로를 적당히 찾기까지 거리 질의를 너무 많이 해야 해서 답답했다. 그래서 더 많은 정보를 얻을 수 있는 질의를 하기로 했다. 정수 K(1 ≤ K ≤ 1,000,000,000)를 입력받아, 거리가 K 이하인 농장 쌍이 몇 쌍인지 알고 싶어 한다. 거리는 한 농장에서 다른 농장까지 이동하는 데 필요한 도로의 길이다. 서로 다른 농장의 쌍만 센다. 예를 들어 (5번 농장, 5번 농장) 같은 쌍은 세지 않는다.
입력
- 1행: 공백으로 구분된 두 정수 N과 M
- 2행부터 M+1행까지: 각 줄에는 도로를 나타내는 네 값 F1, F2, L, D가 공백으로 구분되어 있다. F1과 F2는 도로로 연결된 두 농장의 번호이고, L은 도로의 길이이며, D는 F1에서 F2 방향을 나타내는 문자로 'N', 'E', 'S', 'W' 중 하나이다.
- M+2행: 정수 K 하나.
출력
- 1행: 거리가 K 이하인 농장 쌍의 수.
힌트
길이가 10 이하인 도로는 5개다. 1-4 (3), 4-7 (2), 1-7 (5), 3-5 (7), 3-6 (9)이다.