Настройки поиска (Страница 2 из 2)

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;

const int inf = 1000;

struct ind
{
    int i, num;
};

bool operator < (const ind &a, const ind &b)
{
    return a.num < b.num;
}

int e[101][101];
int n, s, f;
priority_queue < ind> d1;
bool g[101];
vector < int > d(101);

//ifstream cin("input.txt");
//ofstream cout("output.txt");

void dijkstra(int s1, int s2)
{
    int i, j, bj, bd;
    g[s1] = true;
    for (i = 1; i <= n; i++){
        d[i] = e[s1][i];
        ind f;
        f.i = i;
        f.num = -e[s1][i];
        d1.push(f);
    }
    for (i = 1; i < n; i++)
    {
        bj = -1;
        bd = inf;
        ind f;
        f = d1.top();
        /*bool gg = d1.empty();
        if (g[f.i]){
            while (g[f.i] && d1.empty() == false)
            {
                d1.pop();
                f = d1.top();
            }
        }*/
        d1.pop();
        if (d1.empty()) break;
        bj = f.i;
        bd = -f.num;
        if (bj == -1) break;
        g[bj] = true;
        for (j = 1; j <= n; j++)
            if (bd + e[bj][j] < d[j])
            {
                d[j] = bd + e[bj][j];
                f.i = j;
                f.num = -d[j];
                d1.push(f);
            }
    }
    if (d[s2] == inf) cout << "-1";
    else cout << d[s2];    
}


int main()
{
    cin >> n >> s >> f;
    int i, j;
    if (s == f){
        cout << "0";
        return 0;
    }
    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++){
            int k;
            cin >> k;
            if (k == -1 || i == j) e[i][j] = inf;
            else e[i][j] = k;
        }
    for (i = 1; i <= n; i++)
        d[i] = inf;
    dijkstra(s, f);
    return 0;
}