Skip to main content
Učilnica FRI 24/25
  • Home
  • More
Close
Toggle search input
English ‎(en)‎
English ‎(en)‎ Slovenščina ‎(sl)‎ Македонски ‎(mk)‎ Русский ‎(ru)‎ 한국어 ‎(ko)‎
You are currently using guest access
Log in
Učilnica FRI 24/25
Home
Expand all Collapse all
  1. aps1uni
  2. Najkrajše poti
  3. Druga

Druga

Completion requirements
Due: Sunday, 22 December 2024, 11:59 PM

V enostavnem neusmerjenem uteženem grafu z $N$ vozlišči in $M$ povezavami izračunaj dolžino druge najkrajše poti med vozliščema $0$ in $N-1$. Dolžina poti je vsota dolžin vseh povezav na poti. Dovoljene so le poti brez ponavljanja vozlišč. Če bi vse take poti uredili po njihovi dolžini od krajših proti daljšim, nas torej zanima dolžina druge v tem vrstnem redu.

Omejitve podatkov:

  • $1 \leq N \leq 2000$
  • $1 \leq M \leq 10^4$
  • $1 \leq$ dolžina povezave $\leq 10^4$

Vhodni in izhodni podatki:

Prva vrstica vsebuje število vozlišč $N$ (oštevilčimo jih z zaporednimi števili od $0$ do $N-1$) in število povezav $M$. Sledi $M$ trojic oblike $i$ $j$ $k$, kjer sta $i$ in $j$ vozlišči, $k$ pa dolžina povezave med njima.

Na izhodu izpišite iskano dolžino druge najkrajše poti. V primeru, da je najkrajših poti več, je iskana vrednost kar enaka dolžini najkrajše poti. Če vozlišči $0$ in $N-1$ nista povezani ali med njima obstaja natanko ena pot, izpišite -1.

Primeri

Vhod 1:

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

Izhod 1:

5

Vhod 2:

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

Izhod 2:

-1
You are currently using guest access (Log in)
Get the mobile app
Powered by Moodle
Obvestilo o avtorskih pravicah