Yol Planlayıcısı#2567

Yol Planlayıcısı

1 saniyə

64 meqabayt

Çox çətin

Döngüsüz yol şəbəkəsi bir istiqamətli yol seqmentlərindən (kənarlardan) ibarətdir, hər biri $N$ kəsişmədən ikisini (tənha nöqtələr) birləşdirir. Yol seqmentində hərəkət etmək üçün tələb olunan vaxt həmişə müsbətdir və həmin seqment $s$ -dən istifadə edən avtomobillərin sayı $C$ -dən asılı olaraq xətti artır:

$T (s) = a_{S} C + b_{S}$ T(s) = a_S C + b_S

Burada, $a_{S}$ a_S və $b_{S}$ b_S yol seqmenti $s$ -nin parametrlərini təyin edən, tək dəqiqlikli onluq ədəd kimi verilmiş iki sabitdirlər. Kəsişmələrdən keçmək üçün tələb olunan vaxt $0$ -dır.

Bu yol şəbəkəsində bir neçə avtomobil $0$ -cı tənha nöqtədən $N - 1$ N-1-ci tənha nöqtəyə çatmalıdır. Hər bir avtomobil öz trayektoriyasını eqoistcəsinə seçir ki, öz hərəkət müddətini minimuma endirsin, eyni zamanda bütün digər avtomobillərin də belə etdiyini nəzərə alır. Sizin vəzifəniz hər mümkün yol üzrə neçə avtomobilin hərəkət etdiyini və həmin yollar üzrə səyahət üçün tələb olunan vaxtı hesablamaqdan ibarətdir.

Giriş

Giriş faylı bir neçə testdən ibarətdir və belə qurulub. İlk sətirdə testlərin sayı göstərilir. Sonrakı sətirlər testləri təsvir edir. Hər bir test, boşluqla ayrılmış şəkildə nöqtələrin sayı, kənarların sayı və avtomobillərin sayı olan bir sətrlə başlayır. Sonra, hər bir kənar ayrıca sətirdə aşağıdakı sahələrə malikdir: mənbə nöqtəsi, təyinat nöqtəsi, $a_{S}$ a_S və $b_{S}$ b_S.

Çıxış

Hər bir test üçün, şəbəkədə hər hansı bir avtomobil üçün mümkün olan minimal vaxtı, aşağıya doğru tam ədədə yuvarlaqlaşdıraraq, bir sətirdə çap edin.

Qeyd: Birinci giriş $4$ tənha nöqtə və $4$ kənardan ibarətdir; $4000$ avtomobil $0$ -cı nöqtədən $3$ -cü nöqtəyə çatmalıdır. Ən kiçik hərəkət müddətinə nail olmaq üçün, avtomobillər hər iki mümkün yoldan ( $0 - 1 - 3$ 0-1-3 və $0 - 2 - 3$ 0-2-3) bərabər sayda keçir; beləliklə, minimum vaxt $\textbf{lower$ (0.01 * 2000 + 45.1) = 65 $- d i r . I ˙ k in c i g i r i s \c bi r in c ininb ə n z ə r i d i r, amma$ -dir. İkinci giriş birincinin bənzəridir, amma 1 $- c in o ¨ q t ə d ə n$ -ci nöqtədən 2 $- c in o ¨ q t ə y ə s ı f ı r q i y m ə tl ibi r k ə na r ə l a v ə o l u n u b . B u ha l d a, b u ¨ t u ¨ na v t o m o bi l l ə r e q o i s t c ə s in ə ($ -ci nöqtəyə sıfır qiymətli bir kənar əlavə olunub. Bu halda, bütün avtomobillər eqoistcəsinə (0-1-2-3 $) y o l u n u se c \c i r v ə minim u mh ə r ə k ə t m u ¨ dd ə t i$ ) yolunu seçir və minimum hərəkət müddəti 80$-dir.

Nümunələr

Nümunə 1