Informatica Online Judge

  고속도로 톨게이트 [2130 / 0852]

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


The Champion of this Problem (C++) : gs16106 - 0ms / 825byte
My Best Submission (C++) : N/A

[koistudy.net (unkonwn)]
Writer ID : [gs16105]

Background

한 달 정도 남은 새해에 한 평범한 회사원이 여행을 떠나기 위해 목적지까지 가장 빨리 가는 방법에 대해 알아보고자 고속도로 정보를 알아보고 있던 중이었다.

그러던 도중 문득 그는 자신의 차에는 하이패스 기계가 아직 설치되어 있지 않다는 것을 기억해냈다.
하이패스 기계가 없으면 고속도로 중간 중간에 있는 톨게이트를 빠르게 지나갈 수 없다는 것은 이미 잘 알고 있었던 사실이었기 때문에, 고속도로에 있는 톨게이트에 대한 정보를 모두 샅샅이 뒤져보기 시작했다.

결국 t개의 톨게이트가 있다는 것을 알아냈고, 이 톨게이트를 지나가는데 시간이 얼마나 걸리는지 역시 알게 되었다.

하지만 이 때문에 목적지까지 가장 빨리 가는 경로를 처음부터 다시 계산해야 되었고, 이미 지쳐버린 회사원은 이 일을 대신 해줄 사람을 찾고 있다.

톨게이트 사이에는 두 톨게이트 사이를 잇는 h개의 도로가 있으며, 도로 종류는 일반적인 고속도로와 단방향 도로가 있다.

새해이므로 당연히 도로를 지나는데 도로가 밀릴 수도 있으며, 이 때문에 도로를 지나는데 걸리는 시간은 각각의 도로마다 다르다. 당신은 이 회사원을 도와 최단 시간을 찾고자 한다.

Input

첫 줄에 톨게이트 개수 t(3 <= t <= 500), 도로의 개수 h(3 <= h <= 2000), 목적지인 톨게이트 f(2 <= f <= t)가 주어진다.(출발지는 톨게이트 1로 고정되어 있다.)

두 번째 줄부터 t개 줄 동안 각각의 톨게이트에 대해 톨게이트를 지나기 위해 필요한 시간(<=1000)이 차례대로 입력된다. 시작점인 톨게이트 1과 목적지인 톨게이트 f의 경우 반드시 0으로 주어진다.

이후부터 h개 줄 동안 다음 4개의 자료가 차례대로 띄어쓰기로 구분되어 주어진다.
도로가 시작되는 톨게이트 번호
도로가 끝나는 톨게이트 번호
도로를 지나는데 걸리는 시간(<=1000)
도로의 종류(1로 주어지면 고속도로, 2로 주어지면 단방향 도로. 단방향 도로로 주어질 경우 반드시 도로가 시작되는 톨게이트 번호에서 도로가 끝나는 톨게이트 번호로만 향해 갈 수 있다.)

Output

회사원이 여행 목적지까지 걸리는 최단 시간을 출력한다. 목적지까지 가지 못한다면 –1을 출력한다.

IO Example

입력1
4 5 4
0
3
4
0
1 2 5 1
1 3 2 1
3 2 2 2
2 4 4 1
3 4 8 2

출력1
12

example 1 solution
1 -> 3 -> 2 -> 4로 갈 경우 15로 갈 수 있다.
다른 경로의 경우 1 -> 2 -> 4는 12의 시간이, 1 -> 3 -> 4는 14의 시간이 걸린다.
즉, 12의 경우가 가장 짧은 시간이 걸리게 된다.

입력2
3 3 3
0
5
0
1 2 4 2
3 2 5 2
3 1 3 2

출력2
-1

example 2 solution
이 경우 어떤 방법으로도 1에서 3으로 가는 방법이 없다.

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