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

Đọc đề đẹp hơn ở:
https://codeforces.com/group/FLVn1Sc504/contest/274766/problem/Q

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
2019-10-01 10:43:10
ITK17 _NBK: giải thích lại đề cho những thanh niên chưa hiểu, kiểu như là mik phải tìm 1 trong nhưng điểm còn lại ( ko thuộc F) sao cho (tổng thời gian nhỏ nhất từ đỉnh đó đến từng đỉnh trong F) / F là nhỏ nhất :v
2019-09-23 14:54:12
LelouVincx
2019-08-16 01:04:52
58.88 là sao thế anh em
2019-05-12 16:04:44
đọc khó kiểm soát não :v
2019-03-24 03:52:24
vẽ lệch nha mn :V đề bài trình bày sida vl :V
2018-04-15 09:42:22
wtf cái đề ...... :v
2018-03-20 08:27:26
Cái hình vẽ nhìn chả hiểu cái gì, anh em cứ trâu là ăn.
Đề nghị thanh niên AD búng cu 10 lần vì đề thật khó hiểu :v :v :v.
2017-12-22 09:18:22
Hình minh họa rõ ràng này: http://acm.nuc.edu.cn/OJ/problem/show/1362
from PD

Last edit: 2017-12-22 09:21:07
2017-07-12 04:37:40
http://ideone.com/BpNiap
2017-05-29 10:29:35
dùng qhd + bs là AC mà izzzzzzz
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.