apraksts uzdevumi suutiit jauns statuss rezultati helps apraksts

samaksa Maksas ceļi 1 sek.


 Uzdevums

N pilsētas, kas apzīmētas ar naturāliem skaitļiem no 1 līdz N, savieno vienvirziena maksas ceļu sistēma. Katru ceļu raksturo ceļa garums un maksa (izteikta monētu skaitā), kas jāmaksā par šī ceļa lietošanu.

Ceļotājs vēlas nokļūt no pilsētas 1 līdz pilsētai N, bet viņam nav īpaši daudz monētu.

Atrodiet īsāko ceļu no pilsētas 1 līdz pilsētai N, par kuru ceļotājs varētu samaksāt!

 
 Ievaddati

Teksta faila samaksa.in pirmā rinda satur naturālu skaitli K(1<=K<=10000) - ceļotājam piederošo monētu skaitu.
Faila otrajā rindā dots viens naturāls skaitlis - pilsētu skaits N (2<=N<=100).
Faila trešajā rindā dots viens naturāls skaitlis - ceļu kopskaits R (1<=R<=10000).
Katra no nākošajām R faila rindām apraksta vienu ceļu, uzdodot veselu skaitļu vērtības S,D,L un T. Starp katriem diviem blakus skaitļiem ievaddatos ir viens tukšumsimbols.

  • S ir pilsēta, kurā ceļš sākas, 1<=S<=N,
  • D ir pilsēta, kurā ceļš beidzas, 1<=D<=N,
  • L ir ceļa garums, 1<=L<=100,
  • T ir maksa monētās par ceļa lietošanu, 0<=T<=100.

Ievērojiet ka divas pilsētas savā starpā var būt saistītas ar vairāk kā vienu ceļu.

 
 Izvaddati

Teksta faila samaksa.out vienīgajā rindā jāizvada viens vesels skaitlis - īsākais ceļš no pilsētas 1 līdz pilsētai N, maksa par kuru nepārsniedz esošo monētu skaitu.
Ja šāds ceļš neeksistē, failā jāizvada skaitlis -1.

 
 Piemērs

samaksa.insamaksa.out
5
6
7
1 2 2 3
2 4 3 3
3 4 2 4
1 3 4 1
4 6 2 1
3 5 2 0
5 4 3 2
11
samaksa.insamaksa.out
0
4
4
1 4 5 2
1 2 1 0
2 3 1 1
3 4 1 0
-1

 
 Atsauces
Uzdevums izmantots Centrāleiropas valstu informātikas olimpiādē 1998.gadā.

Drukāšanai

 

Copyright © 2001 Girts Folkmanis, LIIS