Wolowitz

Osnovne informacije

Omejitve
  • Čas: 4 s
  • Spomin: 128 MB
Vsebovana v: Avtor:
  • Tine Šukljan
  • UPM 2013

Pošlji rešitev



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

Vaš prijatelj Howard je znan po številu prijateljic, ki jih ima. Vsako noč prespi pri kateri izmed njih. Vsako jutro pa mora naravnost v službo. Na žalost pa je v zadnjem času prevečkrat zamudil, zato mu nadrejeni na Caltech-u grozijo z odpovedjo, če še enkrat zamudi. Domislil se je, da bi si na smartphone za vsako prijateljico shranil tudi podatek o tem koliko je oddaljena od Caltech-a, da bi zjutraj lahko pravočasno prišel v službo.

Ker doma igra D&D in je edina njegova fizična aktivnost obiskovanje prijateljic, so edine ceste, ki jih pozna v Pasadeni, tiste, ki vodijo od prijateljice do prijateljice oz. do Caltech-a. Poleg tega je vsaki prijateljici in Caltech-u dodelil unikatno zaporedno številko, začenši z 0. Ker se Howard vozi z Vespo, se poslužuje samo zakotnih enosmernih ulic.

Ker Howard nima doktorata, ne ve, kako bi izračunal razdalje od vsake prijateljice do Caltech-a (preverjeno obstaja pot od vsake prijateljice do Caltech-a). Tukaj pa nastopite vi.

Naloga

Napišite program, ki izračuna razdaljo od vsake prijateljice (in tudi Caltech-a) do Caltech-a.

Vhodni podatki

V prvi vrstici se nahajata celi števili N in M, kjer je N število prijateljic (poleg je štet tudi Caltech), M pa število cest med njimi.

V drugi vrstici se nahaja Z, tj. zaporedna številka, ki jo je dodelil Caltech-u.

Nato sledi M vrstic oblike: a_i b_i c_i, kjer je a_i zaporedna številka prijateljice, pri kateri se cesta začne, b_i zaporedna številka prijateljice, pri kateri se cesta konča, c_i pa je dolžina ceste.

Omejitve vhodnih podatkov

  • 1 \leq N \leq 5000
  • 1 \leq M \leq 150000
  • 0 \leq Z, a_i, b_i < N
  • 1 \leq c_i \leq 2^{15}

Izhodni podatki

Za vsako prijateljico (in tudi za sam Caltech) izpiši razdaljo do Caltech-a.

Primer

Vhod

5 7
1
0 1 3
0 4 3
2 1 2
2 0 1
3 0 7
3 2 4
4 3 2

Izhod

3
0
2
6
8
Tip: Log in to
  • submit and test your solution
  • post or read questions and answers about this task