Informatica Online Judge

  지하철 [1290 / 050A]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 5   Total Tried : 42


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[koistudy.net (32nd 구재현)]

Background

재현이는 koistudy에 지하철 3호선 문제를 등록하면서 "지하철 1호선 문제를 내겠다!" 라고 다짐했지만, 애석하게도 얼마 안돼서 재현이가 좋은 트리 문제를 낼만큼 창의적이지 않음이 밝혀졌다.

그래서 재현이는 땜빵으로 그냥 지하철 노선도 문제를 내기로 결심했다.

재현이의 도시에는 N개의 지하철 노선이 있으며, 각 노선의 길이는 Li (1 <= Li <= 10^9) 이다. 각 노선들은 모두 고유한 역 번호를 가지며, 역 번호는 순서대로 배정된다 (1 - 2 - 3... Li) 인접한 두 역간에 열차로 다니면서 걸리는 시간은 2분 이며, 정차 시간은 편의상 고려하지 않는다.

또한, 재현이의 도시에는 M개의 환승역이 존재한다.

환승역은 두개의 역을 이으며, 두개의 역을 잇는데 걸리는 시간 Ti를 가진다.

역은 (Ti, Si) 형태로 입력되며, Ti는 노선 번호 (1 <= Ti <= N), Si는 역 번호 (1 <= Si <= L(Ti)) 형태로 주어진다.

환승역은 (T1i, S1i, T2i, S2i, Xi) 형태로 주어지며, 두 역을 환승하는 데 걸리는 시간이 Xi가 걸린다는 것을 의미한다.

재현이의 도시에는 3개 이상의 역이 환승될 수도 있지만, 이는 모두 두개의 역을 잇는 형태로 분리되어서 주어진다.

예를 들어 해당 역에서 1호선 30번, 3호선 29번, 5호선 34번이 환승된다면, 이는 (1,30,3,29,X) / (3,29,5,34,Y) 식으로 주어진다는 것을 의미한다.

이 때, 1호선과 5호선간을 환승하는 데 걸리는 시간은 X + Y분이다.

재현이는 항상 그래왔듯이, 박승원의 집과 신승원의 집을 지하철로 다니는 데 걸리는 시간이 궁금하다.

박승원의 집 근처에 있는 지하철역과, 신승원의 집 근처에 있는 지하철역이 (Ti, Si)의 형태로 두개 주어졌을 때, 두 집간에 걸리는 시간을 출력하라.

시간을 계산할때는 문제에 주어진 조건들만 고려하면 된다.

Input

첫번째 줄에 N, M 이 주어진다.
이후 N개의 줄에 Li 가 주어진다.
이후 M개의 줄에 환승역의 정보가 주어진다. 환승역은 (T1i, S1i, T2i, S2i, Xi) 형태로 주어진다. T1i != T2i임이 보장된다.
마지막 줄에, 신승원의 집 T1, S1과 박승원의 집 T2, S2가 주어진다.

30%의 데이터에 대해서, N <= 10, Li <= 100을 만족한다.


[입력값의 정의역]
1 <= N <= 50000, 1 <= M <= 100,000
1 <= Li <= 10^9

Output

두 역을 잇는데 걸리는 시간을 출력한다. 두 역이 연결되어 있지 않은 경우는 없다.

IO Example

입력1
4 5
100
40
50
50
1 1 2 1 5
2 10 3 10 6
3 30 4 30 2
1 50 4 40 1
3 30 2 30 4
2 14 3 50

출력1
76

설명
[2,14] -> [2,30] -> 4분 환승 -> [3,30] -> [3,50], 76분이 걸린다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]