VACATION - Vacation Planning

Hãng hàng không Bovinia mở các chuyến bay kết nối n cánh đồng nơi những con bò sống. Có k cánh đồng (k ≤ n) trong số các cánh đồng trên được chọn làm trung tâm của hãng. Những cánh đồng được đánh số từ 1 đến n, trong đó các cánh đồng từ 1 đến k là những trung tâm của hãng này.

Có m chuyến bay một chiều kết nối giữa hai cánh đồng. Chuyến bay thứ i đi từ u_i đến v_i, và tốn d_i đô la.

Hãng vừa nhận được một yêu cầu gồm q chuyến du lịch một chiều. Chuyến du lịch thứ i bắt đầu từ a_i đến b_i. Để đi từ a_i đến b_i, chuyến du lịch này có thể bao gồm một dãy các chuyến bay trực tiếp (có thể đi tới một cánh đồng nhiều lần, nhưng nó phải bao gồm ít nhất một trạm trung tâm). Yêu cầu này có thể dẫn đến có một số tuyến không hợp lệ từ a_i đến b_i. Với những tuyến bay hợp lệ, bạn hãy giúp hãng hàng không Bovinia tính xem giá tiền nhỏ nhất của những chuyến bay này.

Input :

- Dòng đầu tiên chứa 4 số nguyên : n, m, k và q

- Dòng 2 -> m + 1 : dòng thứ i + 1 chứa u_i, v_i và d_i của chuyến bay i

- Dòng m + 2 -> m + q + 1 : dòng thứ m + i + 1 mô tả chuyến du lịch thứ i bao gồm a_i và b_i

Output :

- Dòng đầu tiên ghi số chuyến du lịch mà tồn tại một tuyến đường hợp lệ

- Dòng thứ hai ghi tổng số các giá tiền nhỏ nhất của các tuyến hợp lệ cho mỗi chuyến du lịch có tuyến hợp lệ

Giới hạn :

- 1 ≤ n ≤ 200

- 1 ≤ k ≤ 100

- 1 ≤ m ≤ 10000

- 1 ≤ d_i ≤ 1000000

- 1 ≤ q ≤ 10000

Ví dụ :

Input :

3 3 1 3

3 1 10

1 3 10

1 2 7

3 2

2 3

1 2

Output :

2

24


Added by:Kata
Date:2014-03-12
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:USACO Dec 13, Silver Div

hide comments
2018-05-10 16:07:55
use long long for the required number of trips and the sum of the minimum possible route cost. Got 2 WA for not using long long
2015-07-10 21:08:26 peeyush taneja
My 150th
2014-12-02 05:48:37 Nikhil Khurana
i m getting WA after 8th judge...i have tried a lot. con someone plzz give me a corner case ?
2014-03-28 07:54:28 newbie
easy one
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.