Avtocesta

Osnovne informacije

Omejitve
  • Čas: 4 s
  • Spomin: 256 MB
Avtor:
  • Tomaž Hočevar
  • UPM 2018

Pošlji rešitev



Tvoji rezultati.
Nisi poslal še nobene rešitve.
Več »

Minister za infrastrukturo je sklenil, da bo naredil red na slovenskih cestah. Neudobna vožnja med določenimi pari mest, med katerimi pogosto potuje, je presegla vse meje. Odločil se je, da bo določene ceste pretvoril v avtoceste. S tem ne bo zmanjšal samo svojega trpljenja zarad neudobja, ampak tudi količino časa, ki ga zapravi na cesti.

Ker nismo v času vsesplošne gospodarske blaginje, je svoj seznam pogostih relacij oklestil na največ 5 bistvenih parov mest. Svoj cilj želi doseči z izgradnjo čim manj kilometrov avtoceste, saj je to neposredno povezano s stroški. Pomagajte mu z učinkovitim programom, še preden se mu izteče mandat ali pa ga odstavijo.

Vhodni podatki

V prvi vrstici se nahajata število mest N in število cest M, ki so opisane v naslednjih vrsticah. Mesta so oštevilčena s števili od 1 do N. Vsaka cesta je podana z oznakama mest A_i in B_i, ki ju povezuje, in celoštevilsko dolžino D_i. Ceste so dvosmerne in vedno povezujejo dve različni mesti (tj. A_i \neq B_i), lahko pa med istim parom mest obstaja več cest.

V naslednji vrstici sledi število parov mest T, med katerimi želimo potovati izključno po avtocestah. V naslednjih vrsticah so podani pari X_i in Y_i (X_i \neq Y_i). Vsi pari so medsebojno različni.

Omejitve vhodnih podatkov

  • 1 \leq N \leq 50
  • 1 \leq M \leq 10^3
  • 0 \leq D_i \leq 10^5
  • 1 \leq T \leq 5

Izhodni podatki

Izpišite najmanjšo skupno dolžino cest, ki jih moramo pretvoriti v avtoceste, da bo mogoče udobno potovati med podanimi pari mest.

Primer

Vhod

9 11
1 2 59
2 3 52
3 4 72
4 6 50
4 5 37
5 6 34
3 9 30
7 3 78
3 6 71
6 7 26
7 8 54
3
1 2
3 8
8 4

Izhod

260

Komentar

Slika prikazuje zgornji primer, ki temelji na cestnem omrežju v Sloveniji (razdalje so povzete iz aplikacije Google Maps). Če želimo potovati med Koprom in Postojno, Ljubljano in Mariborom ter Mariborom in Novim mestom, moramo zagotoviti najmanj 260 km avtocest, ki so na sliki označene z rdečo barvo.

Slovenija

Tip: Log in to
  • submit and test your solution
  • post or read questions and answers about this task