Deykstra

Giriş

Birinci sətirdə üç tam ədəd $n$, $s$ və $f$ verilir: 1 \leq n \leq 2000, 1 \leq s, f \leq n, burada $n$ — zirvələrin sayı, $s$ — başlanğıc zirvə, $f$ — hədəf zirvədir. Növbəti $n$ sətirdə $n$ tam ədəd var: qoşma matrisi a_{i,j} qeyd olunur. Burada $-1$ o deməkdir ki, $i$-dən $j$-yə kənar yoxdur; sıfırdan böyük və ya sıfıra bərabər istənilən ədəd isə kənarın çəkisidir. Əsas diaqonalda sıfırlar verilir. Zirvələr $1$-dən $n$-ə qədər nömrələnib.

Çıxış

$s$-dən $f$-yə qədər ən qısa məsafəni çap edin, əgər yol yoxdursa, $-1$ çap edin.

Nümunələr