z-cycle
Dat je neusmeren tezinski graf sa A cvorova i M grana. Cvorovi grafa su oznaceni brojevima od 1 do N. Svaka grana povezuje dva razlicita cvora i ima pozitivnu tezinu. Treba odrediti najkracu kruznu putanju koja sadrzi cvorove 1 i N i gde se svaki cvor pojavljuje najvise jedanput. Kruzna putanja je put od cvora 1 do N potencijalno preko nekih cvorova i put od cvora N do cvora 1 potencijalno preko nekih cvorova.
InputPodaci se ucitavaju sa standardnog ulaza. U prvom redu se nalaze brojevi N i M (2 <= N <= 1000, 1 <= M <= 10000), koji predstavlja broj cvorova i grana u grafu. U svakom od sledecih M redova nalaze se tri prirodna broja X , Y i W razdvojeni razmakom (1 <= X , Y <= N, 1 <= W <= 100000), koji oznacavaju da postoji neusmerena grana tezine W koja spaja cvorove X i Y.
OutputNa standardnom izlazu u jednoj liniji stampati duzinu najkrace kruzne putanje koja sadrzi cvorove 1 i N. Garantuje se da postojanje barem jedanog takvog ciklusa.
Input:
Output:
4 6
1 2 1
2 3 1
3 4 1
1 3 2
2 4 2
2 4 5Output:
6Obrazlozenje primera: Ciklus 1 -> 2 -> 4 -> 3 -> 1 je trazeno resenje sa ukupnom tezinom 1 + 2 + 1 + 2 = 6.
Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.