Bessie luôn muốn tối ưu cuộc sống và nhận ra mình thích đến $F$ đồng cỏ yêu thích $F_i$ trong $P$ đồng của Farmer John. Đánh số $1,\ldots,P$; $1\le F\le P$, $1\le P\le500$, $1\le F_i\le P$.

$C$ đường hai chiều nối các đồng (số $1,\ldots,C$, $1\le C\le8,000$) cho phép tới mọi đồng trong trại. Đường $P_i$ có hai đầu $a_i,b_i$ ($1\le a_i,b_i\le P$), đi theo mỗi chiều tốn $T_i$ ($1\le T_i\le892$).

Cô muốn tìm số đồng tốt nhất để ngủ, sao cho khi thức dậy thời gian trung bình đi tới $F$ đồng yêu thích là nhỏ nhất.

Trong bản đồ ví dụ, dấu sao chỉ đồng yêu thích và số trong ngoặc vuông là thời gian đi qua đường.

            1*--[4]--2--[2]--3
                     |       |
                    [3]     [4]
                     |       |
                     4--[3]--5--[1]---6---[6]---7--[7]--8*
                     |       |        |         |
                    [3]     [2]      [1]       [3]
                     |       |        |         |
                    13*      9--[3]--10*--[1]--11*--[3]--12*

Bảng sau cho khoảng cách từ các ứng viên 4,5,6,7,9,10,11,12:

                       * * * * * * Favorites * * * * * *
 Potential      Pasture Pasture Pasture Pasture Pasture Pasture     Average
Best Pasture       1       8      10      11      12      13        Distance
------------      --      --      --      --      --      --      -----------
    4              7      16       5       6       9       3      46/6 = 7.67
    5             10      13       2       3       6       6      40/6 = 6.67
    6             11      12       1       2       5       7      38/6 = 6.33
    7             16       7       4       3       6      12      48/6 = 8.00
    9             12      14       3       4       7       8      48/6 = 8.00
   10             12      11       0       1       4       8      36/6 = 6.00 ** BEST
   11             13      10       1       0       3       9      36/6 = 6.00
   12             16      13       4       3       0      12      48/6 = 8.00

Giả sử các ứng viên này chứa lựa chọn tốt nhất (chương trình phải kiểm tra mọi đồng bằng cách nào đó), nơi ngủ tốt nhất là đồng 10.

Dữ liệu vào

• Dòng 1: $P,F,C$ cách nhau bằng dấu cách.
• Dòng $2,\ldots,F+1$: dòng $i+2$ chứa số nguyên $F_i$.
• Dòng $F+2,\ldots,C+F+1$: dòng $i+F+1$ mô tả đường $i$ bằng $a_i,b_i,T_i$ cách nhau bằng dấu cách.

Dữ liệu ra

• Dòng 1: số nguyên chỉ đồng tốt nhất để ngủ. Nếu nhiều đồng cùng tốt nhất, chọn số nhỏ nhất.

Ví dụ

Dữ liệu vào 1

13 6 15
11
13
10
12
8
1
2 4 3
7 11 3
10 11 1
4 13 3
9 10 3
2 3 2
3 5 4
5 9 2
6 7 6
5 6 1
1 2 4
4 5 3
11 12 3
6 10 1
7 8 7

Dữ liệu ra 1

10

Ghi chú

Như trong đề bài

Như trong đề bài.

Tác giả: Rob Kolstad, 2009