메인 콘텐츠로 건너뛰기
Učilnica FRI 24/25
  • 홈
  • 더 보기
닫기
검색 입력 전환
한국어 ‎(ko)‎
English ‎(en)‎ Slovenščina ‎(sl)‎ Македонски ‎(mk)‎ Русский ‎(ru)‎ 한국어 ‎(ko)‎
손님 계정으로 접속
로그인
Učilnica FRI 24/25
홈
모두 펼치기 모두 접기
  1. aps1uni
  2. Najkrajše poti
  3. Druga

Druga

완료 조건
Due: 일요일, 22 12월 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
손님 계정으로 접속 (로그인)
Get the mobile app
Moodle 제공
Obvestilo o avtorskih pravicah