Nosaukums
Slepenais aģents OO7 (agent_oo7)
Laika limits
1.00s
Atmiņas limits
32.0 MB
Grūtība
44%

Definīcija

Gudrinieku ciema slepenajam aģentam OO7 ir daudzas identitātes. Katru identitāti apliecina viltota pase no konkrētas valsts. Pēc starptautiskajiem likumiem aģents var ar konkrētas valsts pasi pārvietoties tikai uz konkrētām valstīm. Pārējās valstīs ir nepieciešama vīza. Vīza rada risku tikt notvertam. Risks tiek mērīts pārlidojumu skaitā, kuriem ir nepieciešama vīza. Ir zināmi visi aviokompāniju vienvirziena maršruti un valstis, starp kurām katra pase ļauj pārvietoties. Uzdevums ir atrast tādus lidojumus, lai risks būtu minimālais iespējamais un tikai pēc tam ceļā tiktu pavadīts minimālais laiks. Aģentam ir jānokļūst no valsts A uz valsti B, ko vienmēr var izdarīt. Palīdzi aģentam veikt visdrošāko maršrutu visātrāk.


Ievaddatu raksturojums

Ievaddatu pirmajā rindā ir dots valstu skaits 1 ≤ N ≤ 103, aviokompāniju skaits 0 ≤ M ≤ 103, valstu skaits 0 ≤ K ≤ 102, pa kurām ļauj ceļot pases, sākuma valsts 1 ≤ A ≤ N un beigu valsts 1 ≤ BN.

Katrā no nākamajā M rindām tiek dots katras aviokompānijas maršrutu saraksts ar ceļā pavadīto laiku katram maršrutam. Maršruta saraksts sākās ar maršrutu skaitu 1 ≤ c ≤ 103. Katrs maršruts tiek apzīmēts ar 3 vērtībām 0 ≤ a < N (sākuma punkts), 0 ≤ b < N (beigu punkts) un 1 ≤ d ≤ 100 (ceļā pavadītais laiks).

Pēdējā rindā tiek dots saraksts ar K valstīm 0 ≤ v ≤ N, kuru apmeklējumu bez vīzām nodrošina pases.


Izvaddatu raksturojums

Rezultātā pirmajā rindā ir jāizvada 2 skaitļi – mazākais risks un mazākais ceļā pavadītais laiks.
Otrajā rindā ir jāizvada apmeklētās valstis pārvietojoties no A uz B, kuras apmeklējot, tiks veikts vismazākais risks visātrāk. Ja eksistē vairāki šādi maršruti, ir jāizvēlās leksikografiski vismazākā valstis apzīmējošo skaitļu rinda.


Paraugdati

Stdin
5 1 4 0 2
3 0 1 1 1 2 1 3 4 1
0 2 3 4
Stdout
1 2
0 1 2

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.