Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

BESTSPOT - Vị trí tốt nhất

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/bestspot


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 F (1 <= F <= P) cánh đồng yêu thích F_i trong tổng số P (1 <= P <= 500;1 <= F_i <= P) cánh đồng (được đánh số từ 1-> 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 <= C <= 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 <= T_i <= 892) và nối 2 cánh đồng a_i và b_i (1 <= a_i <= P; 1 <= b_i <= 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 F 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 * 'd 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: 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

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

Dữ liệu

  • Dòng 1: 3 số nguyên P,F,C
  • Dòng 2..F+1: Dòng i+2 chứa 1 số Nguyên F_i
  • Dòng F+2..C+F+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.

Kết quả

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 !

Ví dụ

Dữ liệu
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

Kết quả
10

Được gửi lên bởi:Jimmy
Ngày:2009-01-16
Thời gian chạy:0.200s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:USACO January 2008 - Silver Division
Translated by canhteo

hide comments
2016-06-13 16:33:50
duyệt trâu là AC =)))
2015-12-15 11:17:02
zZz
2015-11-11 16:00:52 The Flash
dùng Djisktra +heap 91.67 điểm :v test cuối vẫn tle :v
2014-12-19 16:33:48 Phan Minh Dương
nhìn đề bài k bằng 6 ghi vào bài res:=sum/6. haizzzz
2014-10-20 06:06:50 never give up !!
spend 1 hour for dijkstra heap :)) 300 line

Last edit: 2014-11-08 01:43:20
2014-07-15 14:32:51 KNEO
không cần dijkstra heap cũng AC đc.
2014-07-01 10:51:29 Thcs Ðặng Chánh Kỷ
ac, thêm tý heap vào dijkstra là ac ngay
2014-05-22 04:30:37  
Hiểu thêm về thuật toán Dijkstra :))
2014-04-13 15:26:55 Duc M. Pham
Dijkstra Heap đã AC :D
2013-12-28 15:50:53 WAF|Tommy
dùng ma trận kề bị TLE @@
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.