ALGO heapDijkstra

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

namespace Mlxa {
    using namespace std;
    typedef   long long         ll;

    #define eol                 endl
    template <class A> inline void print(A a) { cout << a << ' '; }
    #define endln               cout << eol
        template <class A>              inline void
    println (A a)               { cout << a << eol; }
        template <class A, class... B>  inline void
    println (A a, B... b)       { print(a); println(b...); }
        template <class It>             void
    printseq (It b, It e)       { for (It i(b); i != e; ++i) cout << *i << ' '; endln; }
    #define read                cin

    #define pb                  push_back
    #define mp                  make_pair
    #define all(x)              begin(x), end(x)
    #define size(x)             int(x.size())

    #define openFiles(name)     freopen(name ".in", "r", stdin), freopen(name ".out", "w", stdout)
    #define fastIO              ios_base::sync_with_stdio(0), cin.tie(0)
} using namespace Mlxa;
const int INF(1e8);

template <class T>
class Heap {
public:
    vector<T> d;
    vector<int> v;  // vertex by place
    vector<int> w;  // place by vertex

    inline void swp (int i, int j) {
        register int temp;
        temp = w[v[i]], w[v[i]] = w[v[j]], w[v[j]] = temp;
        temp = v[i], v[i] = v[j], v[j] = temp;
    }

    void down (register int i) {
        for (register int j(i); i+i+1 < size(v); i = j) {
            int l(i + i + 1), r(l + 1); j = l;
            if (r < size(v) && d[v[r]] < d[v[l]]) j = r;
            if (d[v[j]] < d[v[i]]) swp(i, j);
            else break;
        }
    }
    void up (register int i) {
        for (; d[v[i]] < d[v[(i-1)/2]]; i = (i-1)/2)
            swp(i, (i-1)/2);
    }
    void make () {
        register int i(size(v)>>1);
        while (0 <= i) down(i), -- i;
    }
    int pop () {
        int res = v[0];
        swp(0, size(v) - 1);
        v.pop_back(), down(0);
        return res;
    }
    void relax (int i, const T& to) {
        if (to < d[i]) d[i] = to, up(w[i]);
    }
    Heap (int n) { d.resize(n), v.resize(n), w.resize(n); }
    bool notEmpty () { return !v.empty(); }
    void print() {
        println("HEAP:");
        printseq(all(d));
        printseq(all(v));
        printseq(all(w));
    }
};

int n, st, fi; const int maxN(119);
vector< pair<int, int> > G[maxN];

void start () {
    //stdin = freopen("in.txt", "r", stdin);
    read >> n >> st >> fi; int tmp;
    for (register int i(0); i < n; ++ i)
        for (int j(0); j < n && read >> tmp; ++ j)
            if (tmp >= 0) G[i].emplace_back(j, tmp);
}

int heapDijkstra (int start, int finish) {
    Heap<int> heap(n);
    fill(all(heap.d), +INF); heap.d[start] = 0;
    for (int i(0); i < n; ++ i) heap.w[i] = heap.v[i] = i;
    heap.make();

    while (heap.notEmpty()) {
        //heap.print();
        int v = heap.pop(), dv = heap.d[v];
        for (auto pa : G[v])
            heap.relax(pa.first, dv + pa.second);
    }
    return heap.d[finish];
}

int main () {
    start();
    int res = heapDijkstra(--st, --fi);
    if (res < +INF) println(res);
    else            println(-1);
    return 0;
}