CleverCode

Nosaukums: Kašķīgais tēvocis (tevocis)
Laika limits: 1.00s
Atmiņas limits: 256.0 MB
Grūtība: 50%

Definīcija

Tēvocis ir sakašķējies ar sievu un uz laiku aizgājis prom no mājām. Tā kā tēvocim ir vilciena mēnešbiļete, viņš labprāt braukātu ar vilcieniem un siltajos vagonos sapņotu par mierīgāku dzīvi.

Jums tiks dots visu staciju un to savienojošo dzelzceļu un to garumu (laiku, kāds nepieciešams lai aizbrauktu no vienas stacijas līdz otrai) saraksts. Visi dzelzceļi ir divvirzienu un noteikta posma veikšanai, neatkarīgi no virziena, nepieciešams vienāds laika sprīdis.

Tāpat būs zināmi visu vilcienu atiešanas laiki no gala stacijām un to staciju saraksts, kurām tie brauc cauri. Katrs vilciens apstājas visās stacijās, kurām tas brauc cauri.

Pašā sākumā (pirmajā sekundē) tēvocis ir stacijā ar numuru 1 un viņam ir jāatgriežas šajā stacijā laikā starp sekundēm T1 un T2. Ja vienā un tajā pašā laikā vienā un tajā pašā stacijā atrodas divi vilcieni, tad tēvocis var pārlēkt no viena vilciena uz otru momentāni.

Uzrakstiet programmu, kas nosaka, kā tēvocis var vizināties tā, lai stacijās pavadītais laiks būtu mazākais iespējamais!

Ievaddatu raksturojums

Ievaddatu pirmajā rindā dotas piecu naturālu skaitļu N(staciju skaits,2 ≤N≤1000), P(dzelzceļu skaits), V(vilcienu skaits, 1≤V≤1000), T1 un T2 (1≤T1≤T2 ≤50000) vērtības, kas atdalītas ar tukšumsimboliem. Stacijas ir numurētas ar naturāliem skaitļiem no 1 līdz N pēc kārtas.

Katrā no nākošajām P rindām dots pa viena dzelzceļa aprakstam un satur trīs naturālus skaitļus S1, S2 un T(1≤T≤600), kas atdalīti ar tukšumsimboliem. Tas nozīmē, ka ceļojums no stacijas ar numuru S1 līdz stacijai ar numuru S2 (un otrādi) ilgst tieši T sekundes.

Katra no nākošajām V rindām satur viena vilciena aprakstu. Pirmais skaitlis rindā ir T0 - atiešanas laiks no sākuma stacijas, otrais skaitlis ir NS(1≤NS≤1000) - staciju skaits vilciena maršrutā, ieskaitot sākuma un gala staciju. Nākošie NS skaitļi ir staciju numuri, kam vilciens brauc cauri. Vilciens brauc no sākuma līdz gala stacijai, kur visiem pasažieriem ir jāizkāpj un vilciens paliek stāvot gala stacijā. Starp katriem diviem blakus skaitļiem rindā ir tukšumsimbols.

Izvaddatu raksturojums

Izvaddatu vienīgajā rindā jāizvada viens skaitlis - mazākais iespējamais laiks, kāds tēvocim jāpavada stacijās.

Piezīmes

Uzdevums izmantots Horvātijas .informātikas olimpiādē 2003.gadā

Paraugdati

Stdin

4 4 3 30 35
1 2 5
2 3 2
2 4 7
3 4 3
2 4 1 2 4 3
14 4 3 4 2 3
28 3 3 2 1

Stdout

Stdin

4 6 5 80 100
4 2 6
2 1 16
1 3 17
1 4 19
4 3 9
3 2 10
25 3 1 3 2
25 3 1 2 4
4 4 1 2 3 4
52 4 4 2 1 4
64 4 2 3 4 1

Stdout

Stdin

4 6 7 80 100
4 1 8
1 3 7
3 2 15
1 2 2
2 4 1
4 3 3
50 7 2 4 1 2 4 1 3
25 10 4 3 1 2 4 3 1 2 4 1
6 6 2 1 3 4 2 1
11 5 4 2 3 1 4
52 6 1 2 4 3 2 1
23 5 3 2 4 1 2
21 5 4 2 1 3 2

Stdout

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