#include #include #include #include namespace Mlxa { using namespace std; typedef long long ll; #define eol endl template inline void print(A a) { cout << a << ' '; } #define endln cout << eol template inline void println (A a) { cout << a << eol; } template inline void println (A a, B... b) { print(a); println(b...); } template 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 Heap { public: vector d; vector v; // vertex by place vector 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 > 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 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; }