Vị trí tốt nhất

Điểm: 0,20 (OI)

Giới hạn thời gian: 0.38s

Giới hạn bộ nhớ: 512M

Input: stdin

Output: stdout

Nguồn bài:

USACO January 2008 - Silver DivisionTranslated by canhteo

Dạng bài

Ngôn ngữ cho phép

C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

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 \leq n \leq P)$ cánh đồng yêu thích $F_{i}$ trong tổng số $P$ $(1 \leq P \leq 500$ ; $1 \leq F_{i} \leq P)$ cánh đồng (được đánh số từ 1 $\to 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 \leq C \leq 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 \leq T_{i} \leq 892)$ và nối $2$ cánh đồng $a_{i}$ và $b_{i}$ $(1 \leq a_{i} \leq P$ ; $1 \leq b_{i} \leq 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.

Copy

            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}{llllllll} Cánh đồng & Cánh đồng & Cánh đồng & Cánh đồng & Cánh đồng & Cánh đồng & Trung bình \\ 1 & 8 & 10 & 11 & 12 & 13 & khoảng cách \\ 4 & 7 & 16 & 5 & 6 & 9 & 3 & \frac{46}{6} = 7.67 \\ 5 & 10 & 13 & 2 & 3 & 6 & 6 & \frac{40}{6} = 6.67 \\ 6 & 11 & 12 & 1 & 2 & 5 & 7 & \frac{38}{6} = 6.33 \\ 7 & 16 & 7 & 4 & 3 & 6 & 12 & \frac{48}{6} = 8.00 \\ 9 & 12 & 14 & 3 & 4 & 7 & 8 & \frac{48}{6} = 8.00 \\ 10 & 12 & 11 & 0 & 1 & 4 & 8 & \frac{36}{6} = 6.00 \\ 11 & 13 & 10 & 1 & 0 & 3 & 9 & \frac{36}{6} = 6.00 \\ 12 & 16 & 13 & 4 & 3 & 0 & 12 & \frac{48}{6} = 8.00 \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

Copy

Sample Output

Copy

Bình luận

Hãy đọc nội quy trước khi bình luận.

3

hungtien2202 đã bình luận 1:34:51 sa, 28/11/2023

đề bài có một chút sai sót, dòng n+2...C+n+1 mỗi dòng chứa 3 số nguyên ai,bi,Ti chứ không phải là ai,bi,Fi nhé

-5

trytoheckgg đã bình luận 9:19:22 sa, 24/01/2022

Dijkstra(i-->P)

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.