Çətin Marşrutlar

Olimpiya oyunlarına hazırlıq üçün ölkənizin komandası üçün velosiped təlim marşrutları təklif etmək tapşırılır. Təlim komitəsi ölkənin müxtəlif yerlərində cütlər halında məkanlar arasında marşrutları müəyyənləşdirmək istəyir. Hər bir marşrutun çətinlik səviyyəsi onun təpəliklərinin mailliyi əsasında müəyyən olunmalıdır.

Sizə relyef məlumatları olan bir yol xəritəsi veriləcək. İki və ya daha çox yolun kəsişdiyi hər bir kəsişmə nöqtəsi $x$-, $y$- və $z$-koordinatları ilə müəyyən olunur. Hər bir yol bir kəsişmədən başlayır və digərində bitir, düzdür və digər yollarla üst-üstə düşmür və ya altından keçmir (yəni, körpü və ya tunel yoxdur). Yolda velosiped sürmək üçün çətinlik səviyyəsi $d$ aşağıdakı kimi müəyyən olunur: əgər yol düz və ya eniş istiqamətindədirsə, d=0; əgər yol düz olmayan qalxma istiqamətindədirsə, çətinlik d = 100 \cdot \text{rise}/\text{run} olur, burada $\text{rise}$ yüksəklikdəki mütləq dəyişmə, $\text{run}$ isə yolun iki kəsişmə nöqtəsi arasındakı məsafənin z=0 hündürlükdəki $2$D müstəviyə proyeksiyasında olan məsafəsidir. Qeyd: yolun eniş istiqaməti üzrə çətinlik həmişə sıfırdır.

Bir marşrut — ardıcıl yollar silsiləsidir, burada hər növbəti yol əvvəlkinin bitdiyi kəsişmədən davam edir — çətinlik səviyyəsi $d$ sayılır, əgər marşrutdakı bütün yollar arasında maksimum çətinlik $d$-yə bərabərdirsə. Komitə həm də istəyir ki, əgər seçilmiş iki məkan arasında belə çətinlik səviyyəli bir marşrut varsa, ən qısa uzunluğa malik marşrut seçilsin.

Xatırlatma: Döşəmə funksiyası $X$ — $X$-in tam hissəyə qədər kəsilməsi deməkdir.