Informatica Online Judge

  물건 배송 [1115 / 045B]

Time Limit(Test case) : 6000(ms)
Number of users who solved : 9   Total Tried : 15


The Champion of this Problem (C++) : jjwdi0 - 522ms / 1058byte
My Best Submission (C++) : N/A

[CCC2009S]

Background

N개의 도시가 있고, 각 도시들로 연결되는 T개의 배송 경로가 있다.

어떤 두 도시 x, y 사이의 배송 경로로 물건을 배달하기 위해서는 C(x, y) 만큼의 비용이 필요하다.


N개의 도시들 중 K개의 도시에는, 아주 좋은 연필을 판매하는 온라인 상점이 있고, 어떤 도시 x의 상점에서 판매되는 연필의 가격은 Px이다.


어떤 도시 D로 연필을 배송할 때의 최소 구입비(연필가격+배송비)를 찾는 것이 이 문제의 목표이다. 만약, 어떤 도시 D에서 그 D도시로 배송한다면 배송비는 0이다.

Input

첫 번째 줄에는 도시의 개수(N)가 주어진다. 도시들은 1번부터 N번까지로 생각할 수 있다.
두 번째 줄에는 배송 경로의 개수(T)가 주어진다.

다음 T개의 줄에는 3개의 정수 x y C(x, y) 가 도시 사이의 배송비로 주어진다.

그 다음 줄에는 상점이 있는 도시의 개수(K)가 주어진다.

그 다음 K개의 줄에는 2개의 정수 z Pz가 주어지는데 어떤 도시 z에서의 연필가격이 Pz이다.

마지막 줄에는 배달해야할 도시 D가 주어진다.

[Sub-Task Info]
- 100%의 데이터에 대해서 다음 조건을 만족한다.
N <= 5000; 0 <= T <= 25,000,000 ;
0 <= C(x, y) <= 10000, C(x,y) == C(y,x) ;
1 <= K <= N ; 0 <= Px <= 10000 ; 1 <= D <= N

Output

D 도시로 배달할 때의 최소 구입비를 출력한다.

IO Example

입력
3
3
1 2 4
2 3 2
1 3 3
3
1 14
2 8
3 3
1

출력
6

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