| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 2048 MB | 5 | 3 | 3 | 60.000% |
Marin i Vedran vode tim izviđača u višednevnom putovanju kroz Sloveniju. Na njihovim mapama nalaze se $N$ sela označenih brojevima od 1ドル$ do $N$. Među njima su i početno selo $s$ i ciljano selo $t$.
Svaki od njih se samostalno pripremio za ovo putovanje pa ima svoju mapu staza koje povezuju sela. Obje mape možemo predstaviti kao neusmjereni težinski graf te za obje mape vrijedi da je iz svakog sela moguće doći do svakog drugog sela.
Organizirali su se tako da danju Marin tim povede jednom stazom iz svoje mape, dok navečer Vedran vodi tim jednom stazom iz svoje mape te se tako ponavlja iz dana u dan sve dok u nekom trenutku tim ne dođe do ciljanog sela $t$ (bez obzira na to koji je od njih vodio u tom trenutku).
Obojica se savjetuju o tome koju stazu odabrati s Ivanom koji im zapravo želi napakostiti, ali oni to ne znaju.
Prije svakog odabira Marin, odnosno Vedran se savjetuju s Ivanom te im on preporuči neku stazu. Kako ne bi ništa posumnjali staza koju odabire Ivan bit će takva da vrijedi da se udaljenost do ciljanog sela $t$ nakon prolaska stazom strogo smanji (kada bi udaljenost računali samo s mapom od osobe koja vodi tim u trenutku).
Pomozite Ivanu izračunati kolika je najveća moguća udaljenost kojom on može voditi tim do ciljanog sela $t,ドル tako da nitko ništa ne posumnja ili odgonetnite da Ivan tim može po Sloveniji voditi zauvijek.
Ekspedicija počinje po danu iz sela $s,ドル odnosno Marin je taj koji prvi vodi stazom.
U prvom su retku brojevi $N,ドル $s$ i $t$ (2ドル ≤ N ≤ 1000,ドル 1ドル ≤ s, t ≤ N$).
Slijede dva bloka koja opisuju prvo Marinovu pa Vedranovu mapu. U prvom retku bloka nalazi se broj $M$ ($N - 1 ≤ M ≤ 10^5$), broj staza u mapi. U sljedećih $M$ redaka nalaze se tri prirodna broja $u,ドル $v$ i $w$ (1ドル ≤ u, v ≤ N,ドル 1ドル ≤ w ≤ 10^6$) koji označavaju da u pripadajućoj mapi postoji staza duljine $w$ između $u$ i $v$.
U prvom retku ispišite traženu maksimalnu duljinu rute ili -1 ako je Ivanu tim moguće rutirati u nedogled.
5 1 5 5 1 2 2 1 4 2 2 3 1 3 4 1 5 3 1 4 1 2 2 2 4 2 2 3 1 2 5 2
-1
3 1 3 4 1 2 10 2 3 10 1 3 20 2 3 30 4 2 1 10 1 3 10 1 1 10 2 3 10
20
Pojašnjenje prvog probnog primjera: Prvog dana po danu Ivan će Marnina navesti u iz početnog grada 1ドル$ u grad 4ドル$. Navečer će Ivan Vedranu odabrati stazu između 4ドル$ i 2ドル$. Drugog dana, Ivan Marina navodi iz grada 2ドル$ u grad 3ドル,ドル a zatim Vedrana iz grada 3ドル$ u grad 2ドル$. Svaki idući dan može učiniti isto pa je moguće rutirati u nedogled.
Na prvoj slici je Marinova mapa, na drugoj Vedrana, a na trećoj je plan kojim ih vodi Ivan.