| Zgłaszanie | Wszystkie zgłoszenia | Najlepsze | Lista |
WILCZKI - Magda-Wilczki |
Magda, którą znacie z zadania o ciasteczkach, ma poważny problem. Chce mieć zwierzątko domowe. Ale nie jakiegoś psa, kota, czy chomika, ale wilka, a najlepiej kilka. Niestety jej rodzice nie chcą mieć w domu groźnych zwierząt. Postanowiła, bez ich wiedzy i zgody, wybrać się do lasu i złapać sobie czworonożnych przyjaciół.
Przygotowała już mapę lasu, na której zaznaczyła wszystkie ścieżki, polany na których przebywają wilczki oraz ich kryjówkę. Zastanawia się teraz, czy cała ta wyprawa ma sens, tzn. czy uda jej się złapać minimum jednego wilczka. W chwili, gdy Magda pojawi się w lesie (na polanie oznaczonej numerem 1), wszystkie wilczki zaczną uciekać najkrótszą drogą do kryjówki, a Magda zacznie je łapać. Aby złapać wilczka, Magda i dany wilczek muszą znajdować się w pewnym momencie na tej samej polanie. Dzięki swoim niezwykłym zdolnościom, w danej chwili Magda może złapać nieskończenie wiele wilczków.
Przygotowała już mapę lasu, na której zaznaczyła wszystkie ścieżki, polany na których przebywają wilczki oraz ich kryjówkę. Zastanawia się teraz, czy cała ta wyprawa ma sens, tzn. czy uda jej się złapać minimum jednego wilczka. W chwili, gdy Magda pojawi się w lesie (na polanie oznaczonej numerem 1), wszystkie wilczki zaczną uciekać najkrótszą drogą do kryjówki, a Magda zacznie je łapać. Aby złapać wilczka, Magda i dany wilczek muszą znajdować się w pewnym momencie na tej samej polanie. Dzięki swoim niezwykłym zdolnościom, w danej chwili Magda może złapać nieskończenie wiele wilczków.
Jak się zapewne domyślasz, Twoim zadaniem jest sprawdzić, ile wilczków złapie Magda. Należy założyć, że każda ścieżka w lesie ma taką samą długość, oraz że Magda i wilczki poruszają się z taką samą predkością, Magda nie musi cały czas poruszać się i na polanie z kryjówką może przebywać, przechodzić, łapać (ale tylko jeśli nie są już w kryjówce bo wtedy już za późno).
Input
W pierwszej linii wejścia podana jest ilość polan oraz ilość ścieżek w lesie (P, S<=10^6).
W kolejnych S liniach - opisy ścieżek, tzn. informacja o tym, że dana ścieżka łączy polanę A z polaną B.
Następnie liczba wilczków w lesie - W<=10^6.
W kolejnej linii W liczb - numery polan, na których początkowo znajdują się kolejne wilczki. Na jednej polanie może być kilka wilczków.
W ostatniej linii jedna liczba - numer polany, na której znajduje się kryjówka wilczków.
Output
Jedna liczba - ilość wilczków złapanych przez Magdę, lub napis "Nie", gdy wyprawa nie ma sensu i lepiej żeby Magda została w domu i jadła ciasteczka.
Example 1:
Input:8 8
1 2
2 3
3 4
3 5
2 6
5 6
5 7
6 8
4
4 5 6 7
3
2 3
3 4
3 5
2 6
5 6
5 7
6 8
4
4 5 6 7
3
Output:
2
2
Example 2:
Input:3 2
1 2
2 3
2
2 3
3
2 3
2
2 3
3
Output:
Nie
| Dodane przez: | Marek Mystkowski |
| Data dodania: | 2012-08-26 |
| Limit czasu wykonania programu: | 0.100s-1s |
| Limit długości kodu źródłowego | 50000B |
| Limit pamięci: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Języki programowania: | All except: ASM64 GOSU |