Module: Algoritma Floyd


Problem

10 /10


Perjalanan angkasa lepas

Problem

Dalam MMORPG "Pedagang Angkasa Dalam Talian" kelajuan pergerakan pemain antara bintang dihadkan kepada satu parsec sesaat. Pada kelajuan ini, anda boleh sampai ke bintang terdekat dengan cepat, tetapi ia boleh mengambil masa beberapa jam untuk perjalanan dari satu hujung galaksi ke hujung yang lain. Untuk mempercepatkan perjalanan yang begitu jauh, pencipta permainan membuat beberapa "lubang cacing" — terowong yang menghubungkan dua titik di angkasa, yang membolehkan anda bergerak ke sana ke mari serta-merta antara titik ini.

Tulis program yang mengira masa perjalanan minimum menggunakan maklumat lubang cacing.

Baris input pertama mengandungi integer N (1 ≤ N ≤ 100). Ini diikuti dengan baris yang mengandungi 6 integer — koordinat permulaan (xs,ys,zs) dan tamat (xt,y t,zt) titik perjalanan. Ini diikuti oleh N baris yang mengandungi 6 integer — koordinat hujung "lubang cacing". Semua koordinat diukur dalam parsec dan berada dalam julat dari 0 hingga 10000, dan tiada titik dengan koordinat yang sama.

Cetak masa perjalanan minimum dalam beberapa saat dengan ketepatan sekurang-kurangnya 10&tolak;6.
Contoh

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!

# Input Output
1
1
0 0 0 100 100 0
1 1 1 50 100 10
 52.722246