Enolične poti

Osnovne informacije

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

Pošlji rešitev



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

Napišite program, ki bo izračunal število povezanih grafov (neusmerjenih in neuteženih) z vozlišči označenimi od 1 do N, za katere velja, da je najkrajša pot od vozlišča 1 do vsakega drugega vozlišča enolična.

Vhodni podatki

V prvi vrstici se nahaja število N, tj. število vozlišč grafa.

Omejitve vhodnih podatkov

  • 2 \leq N \leq 300

Izhodni podatki

Ker je iskano število lahko zelo veliko, izpišite ostanek tega števila pri deljenju z 1\,000\,000\,007.

Primeri

Vhod

3

Izhod

4

Vhod

4

Izhod

32

Komentar

Spodnja slika prikazuje vse štiri tovrstne grafe s 3 vozlišči.

N=3

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