The legendary land of Gondor had a network of sparks to quickly alert the entire land of an emergency.

Every spark is manned by an archer with several arrows and instruction in which order to light the other sparks.

More precisely, when his own spark is lit, the archer next to it lights his arrows and shoots one at every other spark that has not yet been lit, in the order in which his instructions say. The archer does so until he is out of arrows (or sparks to shoot at).The archers are very precise so every arrow hits its target. The time or an arrow to travel some distance is equal to that distance, while the time or an archer to shoot all his arrows is negligible. Sauron's army is approaching Gondor so the spark at Minas Tirith has been lit. Write a program that, given the layout o sparks in the coordinate plane, the number of arrows and instructions or every archer, calculates the time indices at which each of the sparks will be lit.


The first line contains an integer N (1 ≤N ≤100),the number o sparks. The sparks are numbered from 1 to N. The spark in Minas Tirith, which has been lit at time 0, is spark number 1.

Each of the following N lines describes one spark. The description of one spark is composed of :

The integers X and Y (1 ≤X,Y ≤1000),the coordinates of the spark;

An integer S (1 ≤S ≤100),the number of arrows;

N-1 distinct integers between 1 and N, the instructions or the archer. The instructions are the order in which, once his spark is lit, the archer will consider shooting arrows at other sparks.

No number will appear more than once in the list, nor will an archer be instructed to shoot an arrow at his own spark.

The input will be such that no two sparks will be lit at the same time.


Output N decimal numbers, each on a single line, the times at which the sparks light up, in order from spark 1 to N. Your output must be accurate to ±0.01.


1 1 1 2 3 4
1 2 1 4 1 3
2 1 1 2 1 4
2 2 1 3 2 1

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


Được gửi lên bởi:sieunhan
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
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.