| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
PWRFAIL - Mất điện |
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/pwrfail
Một cơn bão đã phá hủy 1 số đường dây điện của nông trang! Nông dân John có một bản đồ tất cả N (2 <= N <= 1,000) cây cột điện, để thuận tiện ta đánh số các cột này từ 1->N, mỗi cột này được xác định trên mặt phẳng bởi 2 số nguyên x_i, y_i (-100,000 <= x_i <= 100000; -100,000 <= y_i <= 100,000).
Hiện đang có W (1 <= W <= 10,000) đường dây điện nối các cặp cột điện Pi và Pj (1 <= Pi <= N; 1 <= Pj <= N). John cần mang điện từ cột 1 tới cột N (thông qua các đường dây điện và các cột điện khác).
Cho tọa độ của N cột điện và danh sách những đường dây điện vẫn còn hoạt động. Hãy xác định độ dài nhỏ nhất của các đường dây điện cần thêm để sao cho điện từ cột 1 có thể truyền tới cột N. Biết rằng độ dài tối đa của 1 đường dây điện là 1 số thực M (0.0 < M <= 200,000.0).
Ví dụ, dưới đây là bên trái là bản đồ 9 cột điện và 3 dây nối vẫn còn hoạt động sau cơn bão. Trong ví dụ này, M = 2.0. Cách tốt nhất là ta thêm 2 đường dây điện nối 4-6 và 6-9.
Sau cơn bão Phương án tối ưu
3 . . . 7 9 . . . . . 3 . . . 7 9 . . . . .
/
2 . . 5 6 . . . . . . 2 . . 5 6 . . . . . .
/
1 2-3-4 . 8 . . . . . 1 2-3-4 . 8 . . . . .
| |
0 1 . . . . . . . . . 0 1 . . . . . . . . .
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9
Tổng độ dài là 1.414213562 + 1.414213562 = 2.828427124 .
DỮ LIỆU
- Dòng 1: Hai số nguyên cách nhau bởi dấu cách: N và W
- Dòng 2: Một số thực: M
- Dòng 3..N+2: Mỗi dòng gồm 2 số nguyên cách nhau bởi dấu cách: x_i và y_i
- Dòng N+3..N+2+W: 2 số nguyên cách nhau bởi dấu cách: Pi và Pj
KẾT QUẢ
- Dòng 1: Một số nguyên trên 1 dòng. Nếu không có phương án để cấp điện cho cột N từ cột 1 thì ghi ra -1. Ngược lại, ghi ra 1 số nguyên là tổng độ dài nhỏ nhất nhân với 1000.
- Chú ý không làm tròn, làm giảm tích thu được ở trên.
VÍ DỤ
Dữ liệu 9 3 2.0 0 0 0 1 1 1 2 1 2 2 3 2 3 3 4 1 4 3 1 2 2 3 3 4 Kết quả 2828
GIẢI THÍCH
Như hình bên trên.
| Được gửi lên bởi: | Jimmy |
| Ngày: | 2008-10-22 |
| 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 October 2008 - Qualifying Round |
hide comments
|
|||||||
|
2014-08-12 16:33:33 [$Zeus$]
Sửa hộc cả mặt ra các bác ạ, chỉ bớt đi 1 vòng for thoi là khác ngay :v |
|||||||
|
2014-07-01 17:39:28 Thcs Ðặng Chánh Kỷ
bài cũng lạ dữ liệu x y cho là longint mà để longint không ac nổi phải đưa lên int64 |
|||||||
|
2014-05-20 17:07:24 Thcs Ðặng Chánh Kỷ
code dijkstra heap thì được mỗi 55 chuyển sang code dijkstra thường thì ac, vãi bài Last edit: 2014-07-01 17:37:32 |
|||||||
|
2014-05-20 10:35:55 Lollipop
cái đoạn khái bao a[i].x a[i].y phải khai bao x,y là int64 đẻ longint k AC đâu Last edit: 2014-05-20 10:36:09 |
|||||||
|
2014-05-20 10:21:47 Thanga2pbc
dij ma sao time mat 5s nhi :( |
|||||||
|
2014-05-18 16:18:58
Học được 1 điều hay... hãy cẩn thận với phần khai báo :D |
|||||||
|
2013-11-23 04:01:25 dffff
Thoát meo0123456789 Xem hồ sơ Chấm bài Gửi bài Đề bài Tìm kiếm Xếp hạng Tin tức Giới thiệu Quy định Diễn đàn Liên kết Giờ trên SPOJ 2013-11-23 04 : 01 : 02 Nộp bài Các lần bạn nộp Các bài nộp Làm tốt nhất PS PDF Về danh sách bài Từ tập các bài có trên SPOJ (oi) 3203. Mất điện Mã bài: PWRFAIL Một cơn bão đã phá hủy 1 số đường dây điện của nông trang! Nông dân John có một bản đồ tất cả N (2 <= N <= 1,000) cây cột điện, để thuận tiện ta đánh số các cột này từ 1->N, mỗi cột này được xác định trên mặt phẳng bởi 2 số nguyên x_i, y_i (-100,000 <= x_i <= 100000; -100,000 <= y_i <= 100,000). Hiện đang có W (1 <= W <= 10,000) đường dây điện nối các cặp cột điện Pi và Pj (1 <= Pi <= N; 1 <= Pj <= N). John cần mang điện từ cột 1 tới cột N (thông qua các đường dây điện và các cột điện khác). Cho tọa độ của N cột điện và danh sách những đường dây điện vẫn còn hoạt động. Hãy xác định độ dài nhỏ nhất của các đường dây điện cần thêm để sao cho điện từ cột 1 có thể truyền tới cột N. Biết rằng độ dài tối đa của 1 đường dây điện là 1 số thực M (0.0 < M <= 200,000.0). Ví dụ, dưới đây là bên trái là bản đồ 9 cột điện và 3 dây nối vẫn còn hoạt động sau cơn bão. Trong ví dụ này, M = 2.0. Cách tốt nhất là ta thêm 2 đường dây điện nối 4-6 và 6-9. Sau cơn bão Phương án tối ưu 3 . . . 7 9 . . . . . 3 . . . 7 9 . . . . . / 2 . . 5 6 . . . . . . 2 . . 5 6 . . . . . . / 1 2-3-4 . 8 . . . . . 1 2-3-4 . 8 . . . . . | | 0 1 . . . . . . . . . 0 1 . . . . . . . . . 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 Tổng độ dài là 1.414213562 + 1.414213562 = 2.828427124 . DỮ LIỆU Dòng 1: Hai số nguyên cách nhau bởi dấu cách: N và W Dòng 2: Một số thực: M Dòng 3..N+2: Mỗi dòng gồm 2 số nguyên cách nhau bởi dấu cách: x_i và y_i Dòng N+3..N+2+W: 2 số nguyên cách nhau bởi dấu cách: Pi và Pj KẾT QUẢ Dòng 1: Một số nguyên trên 1 dòng. Nếu không có phương án để cấp điện cho cột N từ cột 1 thì ghi ra -1. Ngược lại, ghi ra 1 số nguyên là tổng độ dài nhỏ nhất nhân với 1000. Chú ý không làm tròn, làm giảm tích thu được ở trên. VÍ DỤ Dữ liệu 9 3 2.0 0 0 0 1 1 1 2 1 2 2 3 2 3 3 4 1 4 3 1 2 2 3 3 4 Kết quả 2828 GIẢI THÍCH Như hình bên trên. Được gửi lên bởi: Duc Ngày: 2008-10-22 Thời gian chạy: 1s Giới hạn mã nguồn: 50000B Memory limit: 256MB Cluster: Pyramid (Intel Pentium III 733 MHz) Ngôn ngữ cho phép: Tất cả ngoại trừ: ERL JS NODEJS PERL 6 Nguồn bài: USACO October 2008 - Qualifying Round hide comments 2013-11-23 03:59:50 vo dai dung (edit) 3203. Mất điện Mã bài: PWRFAIL Một cơn bão đã phá hủy 1 số đường dây điện của nông trang! Nông dân John có một bản đồ tất cả N (2 <= N <= 1,000) cây cột điện, để thuận tiện ta đánh số các cột này từ 1->N, mỗi cột này được xác định trên mặt phẳng bởi 2 số nguyên x_i, y_i (-100,000 <= x_i <= 100000; -100,000 <= y_i <= 100,000). Hiện đang có W (1 <= W <= 10,000) đường dây điện nối các cặp cột điện Pi và Pj (1 <= Pi <= N; 1 <= Pj <= N). John cần mang điện từ cột 1 tới cột N (thông qua các đường dây điện và các cột điện khác). Cho tọa độ của N cột điện và danh sách những đường dây điện vẫn còn hoạt động. Hãy xác định độ dài nhỏ nhất của các đường dây điện cần thêm để sao cho điện từ cột 1 có thể truyền tới cột N. Biết rằng độ dài tối đa của 1 đường dây điện là 1 số thực M (0.0 < M <= 200,000.0). Ví dụ, dưới đây là bên trái là bản đồ cột điện và 3 dây nối vẫn còn hoạt động sau cơn bão. Trong ví dụ này, M = 2.0. Cách tốt nhất là ta thêm 2 đường dây điện nối 4-6 và 6-9. Sau cơn bão Phương án tối ưu 3 . . . 7 9 . . . . . 3 . . 7 9 . . . . . / 2 . . 5 6 . . . . . . 2 . . 5 6 . . . . . . / 1 2-3-4 . 8 . . . . . 1 2-3-4 . 8 . . . . . | | 0 1 . . . . . . . . . 0 1 . . . . . . . . . 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 Tổng độ dài là 1.43562 + 1.413562 = 2.82824 . DỮ LIỆU Dòng 1: Hai số nguyên cách nhau bởi dấu cách: N và W Dòng 2: Một số thực: D Dòng 3..N+4: Mỗi dòng gồm 2 số nguyên cách nhau bởi dấu cách: x_i và y_i Dòng N+1..N+2+W: 2 số nguyên cách nhau bởi dấu cách: Pi và Pj KẾT QUẢ Dòng 1: Một số nguyên trên 1 dòng. Nếu không có phương án để cấp điện cho cột N từ cột 1 thì ghi ra -1. Ngược lại, ghi ra 1 số nguyên là tổng độ dài nhỏ nhất nhân với 1000. Chú ý không làm tròn, làm giảm tích thu được ở trên. VÍ DỤ Dữ liệu 9 3 2.0 0 0 0 1 1 1 2 1 2 2 3 2 3 3 4 1 4 3 1 2 2 4 3 4 Kết quả 2838 GIẢI THÍCH Như hình bên trên. Last edit: 2013-11-23 04:01:01 2011-08-08 03:46:15 Anh chỉ yêu vài em..... Anh Duc cho em hoi la em TLE hay WA voi anh oi :((( Leave a Comment Notes: 1. Don't post any source code here. 2. Please be careful, leave short comments only. Don't spam here. 3. For more discussion (hints, ideas, solutions) please visit our forum. 4. Authors are allowed to delete the post and use html code here (e.g. to provide some useful links). Hiển thị: 800x600 1024x768 đầy đủ vnoi team - 2007-2013 Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ by Sphere Research Labs. |
|||||||
|
2013-11-23 03:59:50 dffff
3203. Mất điện Mã bài: PWRFAIL Một cơn bão đã phá hủy 1 số đường dây điện của nông trang! Nông dân John có một bản đồ tất cả N (2 <= N <= 1,000) cây cột điện, để thuận tiện ta đánh số các cột này từ 1->N, mỗi cột này được xác định trên mặt phẳng bởi 2 số nguyên x_i, y_i (-100,000 <= x_i <= 100000; -100,000 <= y_i <= 100,000). Hiện đang có W (1 <= W <= 10,000) đường dây điện nối các cặp cột điện Pi và Pj (1 <= Pi <= N; 1 <= Pj <= N). John cần mang điện từ cột 1 tới cột N (thông qua các đường dây điện và các cột điện khác). Cho tọa độ của N cột điện và danh sách những đường dây điện vẫn còn hoạt động. Hãy xác định độ dài nhỏ nhất của các đường dây điện cần thêm để sao cho điện từ cột 1 có thể truyền tới cột N. Biết rằng độ dài tối đa của 1 đường dây điện là 1 số thực M (0.0 < M <= 200,000.0). Ví dụ, dưới đây là bên trái là bản đồ cột điện và 3 dây nối vẫn còn hoạt động sau cơn bão. Trong ví dụ này, M = 2.0. Cách tốt nhất là ta thêm 2 đường dây điện nối 4-6 và 6-9. Sau cơn bão Phương án tối ưu 3 . . . 7 9 . . . . . 3 . . 7 9 . . . . . / 2 . . 5 6 . . . . . . 2 . . 5 6 . . . . . . / 1 2-3-4 . 8 . . . . . 1 2-3-4 . 8 . . . . . | | 0 1 . . . . . . . . . 0 1 . . . . . . . . . 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 Tổng độ dài là 1.43562 + 1.413562 = 2.82824 . DỮ LIỆU Dòng 1: Hai số nguyên cách nhau bởi dấu cách: N và W Dòng 2: Một số thực: D Dòng 3..N+4: Mỗi dòng gồm 2 số nguyên cách nhau bởi dấu cách: x_i và y_i Dòng N+1..N+2+W: 2 số nguyên cách nhau bởi dấu cách: Pi và Pj KẾT QUẢ Dòng 1: Một số nguyên trên 1 dòng. Nếu không có phương án để cấp điện cho cột N từ cột 1 thì ghi ra -1. Ngược lại, ghi ra 1 số nguyên là tổng độ dài nhỏ nhất nhân với 1000. Chú ý không làm tròn, làm giảm tích thu được ở trên. VÍ DỤ Dữ liệu 9 3 2.0 0 0 0 1 1 1 2 1 2 2 3 2 3 3 4 1 4 3 1 2 2 4 3 4 Kết quả 2838 GIẢI THÍCH Như hình bên trên. Last edit: 2013-11-23 04:01:01 |
|||||||
|
2011-08-08 03:46:15 trandatbav
Anh Duc cho em hoi la em TLE hay WA voi anh oi :((( |
|||||||
RSS