#include <iostream>
#include <queue>

// OBSŁUGA KOLEJKI //
// queue<int> k;
// k.push(x); //dodaje
// k.front(); //zwraca
// k.pop(); //usuwa
// k.empty(); // zwraca prawede jezeli kolejka jest pusta

using namespace std;

const int N = 5;
int graf[N][N] = { 0,2,0,0,6,0,0,1,3,0,4,0,0,0,2,0,0,1,0,1,3,0,0,0,0 }; //macierz sasiedztwa
int odwiedzony[N] = { 0 }; //0 – nieodwiedzony, 1 – odwiedzony

void init() {
    for (int i = 0; i<N; i++) {
        for (int j = 0; j<N; j++) {
            graf[i][j] = rand() % 2;
            cout << graf[i][j] << " ";
        }
        cout << endl;
    }
}

void BFS(int s) {
    queue<int> kolejka;
    kolejka.push(s);
    odwiedzony[s] = 1;
    while (!kolejka.empty()) {
        int u = kolejka.front();
        kolejka.pop();
        for (int i = 0; i<N; i++) {
            if (graf[u][i] == 1 && odwiedzony[i] == 0) {
                kolejka.push(i);
                odwiedzony[i] = 1;
            }
        }
    }
}

bool isFinished() {
    for (int i = 0; i<N; i++){
        if (odwiedzony[i] == 0)
        {
            return false;
        }
    }
    return true;
}

int min(int droga[])
{
    int minimum = 1000;
    int index = -1;
    for (int i = 0; i<N; i++)
        if ((droga[i] < minimum) && (odwiedzony[i] == 0))
        {
            minimum = droga[i];
            index = i;
        }
    odwiedzony[index] = 1;
    return index;
}

void dijkstra(int s)
{
    int droga[N] = {}; //1000 = nieskonczonosc
    for (int i = 0; i<N; i++)
        droga[i] = 1000;

    int poprzednik[N] = {}; //-1 = brak poprzednika
    for (int i = 0; i<N; i++)
    {
        poprzednik[i] = -1;
    }

    droga[s] = 0;

    while (!isFinished())
    {
        int u = min(droga);
        for (int i = 0; i<N; i++)
            if (graf[u][i] > 0)
                if (droga[i] >(droga[u] + graf[u][i]))
                {
                    droga[i] = droga[u] + graf[u][i];
                    poprzednik[i] = u;
                }
    }

    for(int i=0; i<N; i++)
    cout << i+1 << " droga: " <<  droga[i] << endl;

}

int main(int argc, const char * argv[]) {
    /* zad1 TO DO
    srand(time(NULL));
    init();
    DFS();*/

    /* zad2
    init();
    BFS(0); */

    /*dijkstra*/
     dijkstra(0);


    return 0;
}