소 마라톤
시간 제한1초메모리 제한1024 MB
도로 길이가 주어진 농장 네트워크에서 두 농장 사이의 거리가 가장 긴 쌍의 거리를 구합니다.
문제
농부 John은 미국의 비만 유행 소식을 듣고 소들이 운동을 더 하기를 바란다. 그래서 소들이 달릴 소 마라톤 코스를 만들기로 했다. 코스는 농장 두 곳과 그 사이를 잇는 도로들의 순서로 이루어진 경로를 포함한다. 농부 John은 소들이 최대한 많이 운동하기를 원하므로, 지도에 있는 농장 중 서로 가장 멀리 떨어진 두 농장을 찾고자 한다. 거리는 두 농장 사이 경로에 있는 도로 길이의 합으로 잰다. 가장 멀리 떨어진 농장 쌍 사이의 거리를 구하라.
입력
- 1행: 공백으로 구분된 정수 N과 M
- 2행부터 M+1행까지: 각 줄은 도로 하나를 나타내는 네 값 F1, F2, L, D를 공백으로 구분해 담는다. F1과 F2는 도로로 연결된 두 농장의 번호, L은 도로의 길이, D는 F1에서 F2로 가는 방향으로 'N', 'E', 'S', 'W' 중 하나이다.
- M+2행: Farmer Bob의 질의 개수 K (1 ≤ K ≤ 10,000)를 담은 정수 하나.
- M+3행부터 M+K+2행까지: 각 줄은 Farmer Bob의 질의이며 세 정수 F1, F2, I를 담는다. F1과 F2는 질의에 나오는 두 농장의 번호이고, I (1 ≤ I ≤ M)는 Bob이 이 질의를 하는 시점의 데이터 번호이다. 데이터 번호 1은 입력 데이터의 2행에 해당한다.
출력
1행: 가장 멀리 떨어진 농장 쌍 사이의 거리를 나타내는 정수.
힌트
가장 긴 마라톤 경로는 농장 2에서 도로 4, 1, 6, 3을 지나 농장 5까지 가며, 길이는 20+3+13+9+7=52이다.