vreme | memorija | ulaz | izlaz |
---|---|---|---|
0,35 s | 64 Mb | standardni izlaz | standardni ulaz |
Најкраћи пут између два града
Градови су повезани путевима и за сваки пут је познато време потребно да се прође њиме (време потребно да се прође у једном и у другом смеру не мора бити исто). Напиши програм који одређује најбржи пут између два дата града.
Улаз
Са стандардног улаза се уноси број градова \(n\) (\(1 \leq n \leq 5\cdot 10^4\)), у наредном реду број путева \(m\) (\(1 \leq m \leq n^2-n\)) и затим у наредних \(m\) редова описи путева (два цела броја који представљају редне бројеве градова, који се броје од нуле и након тога позитиван реалан број који представља време да се пут пређе). У последња два реда се налазе редни број стартног и редни број циљног града.
Излаз
На стандардни излаз исписати минимално време потребно да се стигне од
стартног до циљног града, заокружено на пет децимала, а затим, у
наредном реду, редне бројеве градова на путу од старта до циља. Ако се
од старта до циља не може стићи учитаним путевима, само исписати
ne
.
Пример
Улаз
4 6 0 1 1.2 1 2 1.3 0 2 2.0 0 3 5.7 1 3 4.6 2 3 2.1 0 3
Излаз
4.10000 0 2 3
Morate biti ulogovani kako biste poslali zadatak na evaluaciju.