Vị trí tốt nhất


Submit solution

Points: 0.20 (partial)
Time limit: 0.375s
Memory limit: 512M

Problem type

Bessie, luôn luôn muốn cuộc sống của mình tốt hơn, đã thấy rõ rằng cô ta thật sự rất thích ghé thăm \(n\) \((1 \le n \le P)\) cánh đồng yêu thích \(F_i\) trong tổng số \(P\) \((1 \le P \le 500\); \(1 \le F_i \le P)\) cánh đồng (được đánh số từ 1 \(\rightarrow P)\) thuộc sơ hữu của nông dân John.

Bessie biết rằng cô ấy có thể xác định được \(C\) \((1 \le C \le 8000)\) con đường hai chiều (được đánh số \(1\) ...\(C)\) kết nối tất cả các cánh đồng trong toàn bộ nông trại. Ứng với mỗi con đường \(P_i\) là thời gian đi \(T_i\) \((1 \le T_i \le 892)\) và nối \(2\) cánh đồng \(a_i\) và \(b_i\) \((1 \le a_i \le P\); \(1 \le b_i \le P)\).

Bessie muốn tìm cánh đồng tốt nhất để ngủ thỏa mãn bình quân thời gian để đi đến \(n\) cánh đồng yêu thích của cô ta là nhỏ nhất.

Ví dụ, hãy xem xét một nông trang được trình bày như một bản đồ dưới đây, nơi đánh dấu * là cách đồng được yêu thích. Các số trong ngoặc là thời gian tương ứng để di chuyển giữa \(2\) cánh đồ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 đây cho thấy các khoảng cách trung bình nếu nghỉ tại các cánh đồng \(4, 5, 6, 7, 9, 10, 11\), và \(12\): \[\begin{array}{|l|l|l|l|l|l|l|l|} \hline & \mbox{Cánh đồng } & \mbox{Cánh đồng } & \mbox{Cánh đồng } & \mbox{Cánh đồng } & \mbox{Cánh đồng } & \mbox{Cánh đồng } & \mbox{Trung bình} \\ & 1 & 8 & 10 & 11 &12 & 13 & \mbox {khoảng cách} \\ \hline 4 & 7 & 16 & 5 & 6 & 9 & 3 & \frac{46}{6} = 7.67 \\ \hline 5 & 10 & 13 & 2 & 3 & 6 & 6 & \frac{40}{6} = 6.67 \\ \hline 6 & 11 & 12 & 1 & 2 & 5 & 7 & \frac{38}{6} = 6.33 \\ \hline 7 & 16 & 7 & 4 & 3 & 6 & 12 & \frac{48}{6} = 8.00 \\ \hline 9 & 12 & 14 & 3 & 4 & 7 & 8 & \frac{48}{6} = 8.00 \\ \hline 10 & 12 & 11 & 0 & 1 & 4 & 8 & \frac{36}{6} = 6.00 \\ \hline 11 & 13 & 10 & 1 & 0 & 3 & 9 & \frac{36}{6} = 6.00 \\ \hline 12 & 16 & 13 & 4 & 3 & 0 & 12 & \frac{48}{6} = 8.00 \\ \hline \end{array}\]

Kết quả tối ưu là cánh đồng \(10\)

Input

  • Dòng \(1\): \(3\) số nguyên \(P\), \(n\), \(C\)
  • Dòng \(2\) ...\(n + 1\): Dòng \(i + 2\) chứa \(1\) số nguyên \(F_i\)
  • Dòng \(n + 2\) ...\(C + n + 1\): Mỗi dòng chứa \(3\) số Nguyên \(a_i, b_i, F_i\) mô tả \(1\) con đường \(2\) chiều là thời gian di chuyển giữa chúng.

Output

  • Gồm \(1\) dòng duy nhất là cánh đồng được chọn. nếu có nhiều kết quả, chọn cánh đồng có chỉ số nhỏ nhất!

Sample Input

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

Sample Output

10

Comments

There are no comments at the moment.