dijkstra2.cpp

#include <iostream>
#include <vector>

using namespace std;

const int MAX_INT = (~(1 << (sizeof(int) * 8 - 1)));

int main(){

    int n, s, f;
    cin >> n >> s >> f;
    s--; f--;

    int cost[100 * 100], d[100];
    bool visited[100] = {};
    for (int i = 0; i < n * n; i++)
        cin >> cost[i];

    for (int i = 0; i < 100; i++)
        d[i] = MAX_INT;
    d[s] = 0;

    int tmp, tmpi, tmpd, swap;
    vector<int> v;
    v.push_back(s);

    while (!v.empty()){
        tmp = v.back();
        v.pop_back();
        if (visited[tmp])
            continue;
        visited[tmp] = true;
        for (int i = 0; i < n; i++){
            tmpi = tmp * n + i;
            if (!visited[i] && cost[tmpi] > -1){
                tmpd = d[tmp] + cost[tmpi];
                if (tmpd < d[i]){
                    d[i] = tmpd;
                    v.push_back(i);
                    int j = v.size() - 1;
                    while(j > 0 && d[i] > d[v[j - 1]]){
                        swap = v[j];
                        v[j] = v[j - 1];
                        v[--j] = swap;
                    }
                }
            }
        }
    }

    if (d[f] == MAX_INT)
        cout << -1 << endl;
    else
        cout << d[f] << endl;

    return 0;
}