GONDOR - GONDOR

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/gondor


Vùng đất huyền thoại Gondor có một hệ thống truyền tin gồm các tháp canh để báo hiệu trong trường hợp khẩn cấp.

Khi mỗi tháp canh được báo hiệu, nhân viên truyền tin ở tháp đó sẽ ngay lập tức truyền thông tin đến tất cả các tháp chưa được nhận thông tin, và theo 1 thứ tự cho trước. Việc truyền tin xảy ra đồng thời (xem ví dụ 2: ngay khi tháp 1 nhận được tin, thông tin được truyền đến cả tháp 2 và 4 -> thời gian tháp 2 nhận được tin là 2). Tuy nhiên nhân viên truyền tin ở tháp i chỉ có thể truyền thông tin tới không quá s[i] tháp khác. Thời gian để truyền tin giữa 2 tháp bằng khoảng cách giữa 2 tháp đó. Tại thời điểm 0, thông tin bắt đầu được truyền từ tháp 1. Tính thời gian để mỗi tháp nhận được thông tin.

Input

Dòng đầu tiên: N (1<=N<=100) là số lượng tháp. Các tháp đánh số từ 1 đến N.

N dòng tiếp theo, dòng thứ i gồm:

+ Số nguyên X và Y (1<=X,Y<=1000) là tọa độ của tháp trong hệ toạ độ

+ Số nguyên S (1<=S<=100) là số tháp mà tháp đó có thể truyền tin đi

+ N-1 số nguyên phân biệt trong khoảng 1 đến N, là danh sách các tháp mà nhân viên ở tháp i được yêu cầu truyền tin. Nhân viên truyền tin ở tháp này sẽ phải lần lượt truyền thông tin đi theo thứ tự trong danh sách. Không có 2 số nào trùng nhau trong danh sách, và trong danh sách thứ i không chứa số i

Dữ liệu đảm bảo không có 2 tháp nào nhận được tin tại cùng 1 thời điểm.

Output

Gồm N dòng, mỗi dòng chứa một số thực. Dòng thứ i chứa thời gian mà tháp thứ i nhận được thông tin. Kết quả của bạn sẽ được tính là chính xác nếu kết quả sai khác không quá 0.01 so với đáp án.

Example

Input:
4
1 1 1 2 3 4
1 2 1 4 1 3
2 1 1 2 1 4
2 2 1 3 2 1

Output:
0.000000
1.000000
3.000000
2.000000

Input:
5
4 3 2 5 2 4 3
4 5 1 4 1 5 3
4 4 1 1 4 5 2
2 4 1 5 2 3 1
3 4 2 2 4 3 1

Output:
0.000000
2.000000
4.414214
2.414214
1.414214


Được gửi lên bởi:sieunhan
Ngày:2009-01-23
Thời gian chạy:1s
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 PERL6 PYPY RUST SED
Nguồn bài:Croatia national contest 2008

hide comments
2021-05-27 18:00:46
Tham khảo: https://vnspoj.github.io/problems/GONDOR
2019-09-02 09:46:17
ezzzz
2019-06-08 18:55:12
trâu cũng ac :)
2019-03-31 09:03:40
AC in one gooooooooooooooooo :V
2016-09-12 09:30:24 Nguyễn Vĩnh Thịnh
=]] đọc đề tiếng Anh trải nghiệm cảm giác LOTR
2016-07-20 15:29:43
đọc kĩ đề là hiểu ak
bài này dễ đó chứ
2016-05-19 04:26:55 Nguyen Cuong
thanks PS đã giải thích kĩ :D
2015-09-12 13:06:32
tham khảo tại: http://nhatkynghiencuu.blogspot.com/2015/07/gondor-ma-gondor-spoj.html
2015-09-10 15:31:48
THAM KHẢO TẠI https://traitaodo.wordpress.com/2015/09/10/gondor-gondor/

Last edit: 2015-10-02 03:27:06
2015-07-22 05:46:31 Do Hong Huan
Nguyên buổi sáng cài heap=>NZEC, trưa cài ma trận kề AC.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.