Policija

Pradinių duomenų failas:

policija.in  

Rezultatų failas:

policija.out  

Laiko apribojimas:

1 s.  

Atminties apribojimas:

16 Mb.  

Užduotis

Šiame uždavinyje Maksimas ir Linas tęsia savo kelionę (taip, istorija prasidėjo kitame uždavinyje). Iš taško B jiems reikia nuvykti į tašką C. Kaip ir visuomet, Maksimas nori važiuoti trumpiausiu keliu. Negalime atskleisti visų detalių, tačiau šios kelionės metu jiedviems reikia išvengti policijos.

Parašykite programą, kuri rastų trumpiausią įmanomą kelią iš taško B į tašką C, tokį, kuriame nepasitaikytų policija, arba nustatytų, kad tokio kelio nėra.

Pradiniai duomenys

Miesto aprašymas pateikiamas faile pradinių duomenų faile. Pirmoje eilutėje įrašyti penki sveikieji skaičiai: N, B, C, G ir P. N yra sankryžų skaičius (N <= 1000), visos sankryžos sunumeruotos skaičiais nuo 1 iki N. B ir C – tai sankryžų, kuriose kelionę pradės ir baigs mūsų keliautojai, numeriai. G yra gatvių, o P – policijos ekipažų skaičius.

Sekančiose G eilučių įrašyta po tris skaičius u, v ir l, reiškiančių, jog sankryžas u ir v jungia gatvė, kurios ilgis yra l metrų (l <= 5000). Gatvės yra dviejų pusių eismo; dvi sankryžas jungia ne daugiau negu viena gatvė.

Toliau, po vieną eilutėje, faile įrašyta P sankryžų numerių, kuriose budi policijos ekipažai. Tarp šių sankryžų numerių nėra B ir C.

Rezultatai

Rezultatus programa turi įrašyti į rezultatų failą. Jei toks kelias egzistuoja, pirmoje eilutėje turi būti įrašytas trumpiausio kelio ilgis S, o antroje – sankryžų numerių seka, apibūdinanti šį kelią. Seka turi prasidėti numeriu B, baigtis numeriu C. Šioje sekoje neturi būti sankryžų, kuriose budi policijos ekipažai.

Jei yra keli sprendiniai, programa gali pateikti bet kurį iš jų. Jei “saugaus” kelio nėra, programa į pirmą rezultato failo eilutę turi įrašyti -1.

Pavyzdžiai

6 1 6 8 2
1 2 500
1 3 300
1 4 200
2 5 800
2 6 1500
3 5 300
4 5 300
5 6 300
3
4

1600
1 2 5 6

7 1 7 9 2
1 2 1300
1 3 1000
2 4 900
2 5 550
3 4 1100
3 5 1200
4 6 860
5 7 1420
6 7 1170
4
5

-1