#include <iostream>
#include <random>
#include <vector>
#include <algorithm>
#include <set>

//#define DEBUG 0 //(1,2,3)
#define DEBUG_ALLOC_SIZE
//#define USE_VERTEX_DATA

using namespace std;
//                             2                       1
enum ERROR { SUCCESS, VERTEX_DOESNT_EXIST, VERTEX_FORM_DIFF_GRAPHS, EDGE_DOESNT_EXIST, EDGES_FROM_DIF_GRAPHS, POS_ERROR, TO_MUCH_TO_INIT };

template<
#ifdef USE_VERTEX_DATA
    typename VertexType,
#endif
    typename EdgeType>
class Dynamic_Graph {
    class _Edge;
public:
    /*
    Struktura grafu

    tablica graph \/
        1. _Edge->_Edge->_Edge->NULL<-End[1]
        2. _Edge->_Edge->NULL<-End[2]
        3. _Edge->_Edge->_Edge->_Edge->NULL<-End[3]

        unsigned int size_graph = 3

    _Edge:
        unsigned int connected_to
        _Edge* next;
    */
    class Edge;
    class Edge_Iterator;

    class Vertex {
    public:
#ifdef USE_VERTEX_DATA
        VertexType& get_props() {
            return graph->data[id];
        }
#endif

        Edge_Iterator iter_begin() {
            return Edge_Iterator(*this);
        }
        const unsigned int get_id() const {
            return id;
        }

        Dynamic_Graph<
#ifdef USE_VERTEX_DATA
            VertexType,
#endif
            EdgeType>&
        get_graph()
        {
            return *graph;
        }
        bool isConnected(Vertex to) {
            return graph->is_connected(id, to.get_id());
        }
        Vertex(
            Dynamic_Graph<
#ifdef USE_VERTEX_DATA
            VertexType,
#endif
            EdgeType>& _graph, unsigned int i)
        {
            graph = &(_graph);
            id = i;
        }
        Vertex() {
            graph = NULL;
            id = -1;
        }
    private:
        Dynamic_Graph<
#ifdef USE_VERTEX_DATA
            VertexType,
#endif
            EdgeType>* graph;
        unsigned int id;

        friend Dynamic_Graph<
#ifdef USE_VERTEX_DATA
            VertexType,
#endif
            EdgeType>;
        friend Edge;
        friend Edge_Iterator;
    };

    class Edge {
    public:
        //Konstruktor
        Edge(Dynamic_Graph<
#ifdef USE_VERTEX_DATA
            VertexType,
#endif
            EdgeType>& _graph, unsigned int _from, unsigned int _to)
        {
            graph = &(_graph);
            from = _from;
            _exist = graph->find_edge(from, _to, To);
        }

        Edge(Vertex& _from, Vertex& _to) {
            graph = (_from.graph);
            from = _from.get_id();
            _exist = graph->find_edge(from,_to.get_id(),To);
        }

        bool exist() {
            return _exist;
        }
        EdgeType& get_props() {
            return To->data;
        }
#ifdef USE_VERTEX_DATA
        VertexType& get_vertex_from_props() {
            return graph->data[from];
        }
        VertexType& get_vertex_to_props() {
            return graph->data[To->connection_to];
        }
#endif
        Vertex get_vertex_to() {
            return Vertex(*graph, To->connection_to);
        }
        Vertex get_vertex_from() {
            return Vertex(*graph, from);
        }
        bool check_if_edge_exist() {
            //TODO
        }
    private:
        //Nie przypisać _to z innego źródła anizeli _from
        Edge(
            Dynamic_Graph<
#ifdef USE_VERTEX_DATA
            VertexType,
#endif
            EdgeType>& _graph, unsigned int _from, _Edge * _to) {
            graph = &(_graph);
            from = _from;
            To = _to;
            _exist = true;
        }
        Dynamic_Graph<
#ifdef USE_VERTEX_DATA
            VertexType,
#endif
            EdgeType>* graph;
        unsigned int from; //Z kad
        _Edge* To; //Do kad
        bool _exist;

        friend Dynamic_Graph<
#ifdef USE_VERTEX_DATA
            VertexType,
#endif
            EdgeType>;
        friend Vertex;
        friend Edge_Iterator;
    };

    class Edge_Iterator {
    public:
        Edge_Iterator(Vertex& Begin) {
            graph = Begin.graph;
            buff = &(graph->graph[Begin.get_id()]);
            begin = Begin.get_id();
        }
        Edge_Iterator(Dynamic_Graph<
#ifdef USE_VERTEX_DATA
            VertexType,
#endif
            EdgeType>& _graph, unsigned int Begin) {
            graph = &_graph;
            buff = &(graph->graph[Begin]);
            begin = Begin;
        }
        Edge_Iterator& operator ++(const int) {
            buff = buff->next;
            return *this;
        }
        const bool is_end() const {
            if (buff == NULL || graph->end[begin] == NULL) {
                return false;
            }
            return true;
        }
        Edge operator*() const {
            return Edge(*graph, begin, buff);
        }
        EdgeType get_edge_props() {
            return buff->data;
        }
        Vertex get_connection_to() {
            return Vertex(*graph, buff->connection_to);
        }
        unsigned int get_connection_to_id() {
            return buff->connection_to;
        }
    private:
        unsigned int begin;
        _Edge* buff;
        Dynamic_Graph<
#ifdef USE_VERTEX_DATA
            VertexType,
#endif
            EdgeType>* graph;

        friend Vertex;
        friend Edge;
    };

template<typename T>
    class Vertex_data {
    public:
        Vertex_data(Dynamic_Graph<
#ifdef USE_VERTEX_DATA
            VertexType,
#endif
            EdgeType>& _graph)
        {
            graph = &_graph;
            data = new T[_graph.get_vertex_count()];
        }
        T & operator ()(const unsigned int a) {
            return data[a];
        }
        T& operator ()(Dynamic_Graph<
#ifdef USE_VERTEX_DATA
                VertexType,
#endif
                EdgeType>::Vertex a)
        {
            return data[a.id];
        }
        friend std::ostream& operator<< (std::ostream& s, const Dynamic_Graph<
#ifdef USE_VERTEX_DATA
            VertexType,
#endif
            EdgeType>::Vertex_data<T> & _graph)
        {
            for (int i = 0; i < _graph.get_size(); i++)
            {
                s << i << "\t" << _graph.data[i] << endl;
            }
            return s;
        }
        const unsigned int get_size() const {
            return graph->get_vertex_count();
        }
    private:
        T * data;

        Dynamic_Graph<
#ifdef USE_VERTEX_DATA
            VertexType,
#endif
            EdgeType>* graph;
    };

    Dynamic_Graph(unsigned int n) : vertex_count(n) {
        graph = new _Edge[n];
#ifdef USE_VERTEX_DATA
        data = new VertexType[n];
#endif
        end = new _Edge * [n];

        for (unsigned int i = 0; i < n; i++)
        {
            end[i] = NULL;
        }
        cout << "alloc: " << sizeof(_Edge) * n + sizeof(_Edge*) * n + sizeof(this)
#ifdef USE_VERTEX_DATA
            + sizeof(VertexType) * n
#endif
            << " bytes" << endl;
    }
#ifdef USE_VERTEX_DATA
    Dynamic_Graph(unsigned int n, VertexType* _data) : vertex_count(n) {
        graph = new _Edge[n];
        data = new VertexType[n];
        end = new _Edge * [n];

        for (unsigned int i = 0; i < n; i++)
        {
            end[i] = NULL;
            data[i] = _data[i];
        }
    }
#endif
    ~Dynamic_Graph() {
        delete[] graph;
#ifdef USE_VERTEX_DATA
        delete[] data;
        delete[] end;
#endif
    }
    //Dodaje krawedz
    void addEdge(unsigned int from, unsigned int to, EdgeType data) {
        add_edge(data, from, to);
    }
    //Zwraca ilosc wierzchołków
    const unsigned int get_vertex_count() {
        return vertex_count;
    }
    //Zwraca wierzcholek
    Vertex get_vertex(unsigned int id) {
        return Vertex(*this, id);
    }
    //Zwraca wlasnosci wierzcholka
#ifdef USE_VERTEX_DATA
    VertexType & get_vertex_props(unsigned int id) {
        return data[id];
    }
#endif
    //Zwraca iterator po krawedziach
    Edge_Iterator get_edge_iterator_from(Vertex from) {
        return Edge_Iterator(from);
    }
    //Zwraca iterator po krawedziach
    Edge_Iterator get_edge_iterator_from(unsigned int from) {
        return Edge_Iterator(*this, from);
    }
    //Zwraca wlasnosci krawedzi
    Edge get_edge(Vertex& from, Vertex& to) {
        return get_edge(from.get_id(), to.get_id());
    }
    //Zwraca krawedz
    Edge get_edge(unsigned int from, unsigned int to) {
        return Edge(*this, from, to);
    }
    //Zwraca wlasnosci krawedzi
    EdgeType & get_edge_props(Vertex& from, Vertex& to) {
        get_edge_props(from.get_id(), to.get_id());
    }
    //Zwraca wlasnosci krawedzi
    EdgeType & get_edge_props(unsigned int from, unsigned int to) {
        _Edge* handeler;
        if (find_edge(from, to, handeler)) {
            return handeler->data;
        }//Krawedz nie istnieje
    }
template<typename T>
    Vertex_data<T> create_vertex_data() {
        return Vertex_data<T>(*this);
    }
    //sprawdza czy istnije polaczenie miedzy from a to O(n)
    bool is_connected(Vertex & from, Vertex & to) {
        return is_connected(from.get_id(), to.get_id());
    }
    //sprawdza czy istnije polaczenie miedzy from a to O(n)
    bool is_connected(unsigned int from, unsigned int to) {
        _Edge* buff = &graph[from];
        while (true) {
            if (buff == NULL) {
                return false;
            }
            if (buff->connection_to == to) {
                return true;
            }
            buff = buff->next;
        }
    }
private:
    struct _Edge {
    public:
        unsigned int connection_to;
        _Edge* next = NULL;
        EdgeType data;


        _Edge(EdgeType& _data) : data(_data) {}
        _Edge(EdgeType& _data, unsigned int _connection_to) : data(_data), connection_to(_connection_to) {}
        _Edge() : connection_to(-1) {}
    };

    //Szuka krawedzi w tablicy, O(n)
    bool find_edge(unsigned int from, unsigned int connected_to, _Edge *& source) {
        _Edge* buff = &graph[from];
        while (true) {
            if (buff == NULL) {
                source = NULL;
                return false;
            }
            if (buff->connection_to == connected_to) {
                source = buff;
                return true;
            }
            buff = buff->next;
        }
    }
    //sprawdza czy istnije polaczenie miedzy from a to
    bool is_connected(_Edge from, unsigned int to) {
        return from.connection_to == to;
    }
    //Dodaje krawedz do grafu O(1)
    void add_edge(EdgeType& data, unsigned int from, unsigned int to) {
        if (end[from] == NULL) {
            graph[from].data = data;
            end[from] = &(graph[from]);
            graph[from].connection_to = to;
        }
        else {
            end[from]->next = new _Edge(data, to);
            end[from] = end[from]->next;
        }
    }
    _Edge* graph;
    _Edge** end;
#ifdef USE_VERTEX_DATA
    VertexType* data;
#endif
    const unsigned int vertex_count;

    friend Vertex;
    friend Edge;
    friend Edge_Iterator;

};

//Wysoka wydajnosc w przypadku gestego grafu (wysoki stosunek ilosci krawedzi do ilosci wierzcholkow), Złożoność pamięciowa: V+E*E
template<typename VertexType, typename EdgeType>
class Static_Graph {
    class _Edge;
    class _vertex;
public:

    //########################################//
    //             KLASY PUBLICZNE            //
    //########################################//

    class Vertex;
    class Edge;

    //Iterator po krawedziach
    class Edge_Iterator {
    public:
        Edge_Iterator(Vertex& _Vertex) {
            vertex = &_Vertex;
            max = vertex->graph->vertexscount - 1;
            iter = 0;

            while (true) {
                if (iter > max || vertex->graph->get(vertex->id, iter)->connected) {
                    break;
                }
                iter++;
            }

        }
        Edge_Iterator& operator ++(const int) {
            iter++;
            while (true) {
                if (iter > max || vertex->graph->get(vertex->id, iter)->connected) {
                    break;
                }
                iter++;
            }
            return *this;
        }
        bool operator<(const unsigned int& a) {
            return iter < a;
        }
        Edge operator*() const {
            return Edge(vertex->graph->pos(vertex->id, iter), vertex->get_Graph(), vertex->id, iter);
        }
    private:
        unsigned int iter;
        unsigned int max;
        Vertex* vertex;

        friend Edge;
        friend Vertex;
    };

    //Publiczna klasa Wierzcholka
    class Vertex {
    public:
        //Konstruktor - _graph - graf, vertex - numer wierzcholka
        Vertex() {
            graph = NULL;
            id = -1;
        }
        Vertex(Static_Graph& _graph, unsigned int vertex) {

#if DEBUG > 1
            if (_graph.vertexscount > vertex) {
                graph = &_graph;
                id = vertex;
            }
#if DEBUG > 2
            else {
                throw VERTEX_DOESNT_EXIST;
                graph = NULL;
                id = -1;
            }
#endif
#else
            graph = &_graph;
            id = vertex;
#endif

        }
        //Stworz iterator iterujacy po krawedziach wychodzacych z wierzcholka
        Edge_Iterator iter_begin() {
            return Edge_Iterator(*this);
        }
        inline unsigned int iter_end() const {
            return graph->vertexscount;
        }
        VertexType& get_props() const {
            return graph->vertexes[id].get_props();
        }
        bool isConnected(const Vertex& a) {
#if DEBUG > 1
            if (a.graph == this->graph) {
                return a.graph->pos(a.id, this->id)->connected;
            }
            else {
#if DEBUG > 2
                throw VERTEX_FORM_DIFF_GRAPHS;
#endif
                return false;
            }
#else
            return a.graph->pos(a.id, this->id)->connected;
#endif
        }
        bool areFromSameGraph(const Vertex& a) {
            return (&a == this);
        }
        unsigned int get_id() const {
            return id;
        }
        Static_Graph* get_Graph() {
#if DEBUG > 1
            if (graph == NULL) {
                throw VERTEX_DOESNT_EXIST;
            }
#endif
            return graph;
        }
    private:

        friend Edge_Iterator;
        friend Edge;
        Static_Graph* graph;
        unsigned int id;
    };

    //Publiczna Klasa krawedzi
    class Edge {
    public:
        //Stworz "handler"'a odwolujacego sie do danych krawedzi
        Edge(Vertex& a, Vertex& b) {
#ifdef DEBUG
            if (a.graph == b.graph) {
                Graph = a.get_Graph();
                if (a.graph->pos(a.id, b.id)->connected) {
                    edge = a.graph->pos(a.id, b.id);
                    x = a.id;
                    y = b.id;
                    _exist = true;
                }
                else {
#if DEBUG > 2
                    throw EDGE_DOESNT_EXIST;
#endif
                    _exist = false;
                }
            }
            else {
#if DEBUG > 1
                throw EDGES_FROM_DIF_GRAPHS;
#endif
                _exist = false;
            }
#else
            if (a.graph->pos(a.id, b.id)->connected) {
                edge = a.graph->pos(a.id, b.id);
                x = a.id;
                y = b.id;
                _exist = true;
            }
            else {
                x = -1;
                y = -1;
                _exist = false;
            }

#endif
        }

        Edge(unsigned int a, unsigned int b, Static_Graph* graph) {
#ifdef DEBUG
            Graph = graph;
            if (graph->pos(a, b)->connected) {
                edge = graph->pos(a, b);
                x = a;
                y = b;
                _exist = true;
            }
            else {
#if DEBUG > 2
                throw EDGE_DOESNT_EXIST;
#endif
                _exist = false;
            }
#else
            Graph = graph;
            if (graph->pos(a, b)->connected) {
                edge = graph->pos(a, b);
                x = a;
                y = b;
                _exist = true;
            }
            else {
                _exist = false;
            }
#endif
        }

        //Pobierz wlasnosci krawedzi
        EdgeType& get_props() {
            if (_exist) {
                return edge->get_props();
            }
#if DEBUG > 2
            else {
                throw EDGE_DOESNT_EXIST;
            }
#endif
        }
        //Pobierz wierzcholek z ktorego wychodzi ta krawedz
        Vertex get_neighbor_form() {
            return Vertex(*(this->Graph), x);
        }
        //Pobierz wierzcholek do ktorego prowadzi ta krawedz
        Vertex get_neighbor_to() {
            return Vertex(*(this->Graph), y);
        }

        //Pobierz wlasciwosci wierzcholka z ktorego wychodzi ta krawedz
        VertexType get_neighbor_props_form() {
            return Graph->vertexes[x].get_props(); //############################################ SPRAWDZIĆ CZY TU NIE POWINNO BYC Y
        }
        //Pobierz wlasciwosci wierzcholka do ktorego prowadzi ta krawedz
        VertexType get_neighbor_props_to() {
            return Graph->vertexes[y].get_props(); //############################################ SPRAWDZIĆ CZY TU NIE POWINNO BYC X
        }

        //Czy krawedz istnieje?
        const bool exist() const {
            return _exist;
        }
    private:
        Edge(Static_Graph::_Edge* _edge, Static_Graph* _Graph, unsigned int _x, unsigned int _y) {
#ifdef DEBUG
            if (_edge->connected) {
                Graph = _Graph;
                edge = _edge;
                x = _x;
                y = _y;
                _exist = true;
            }
            else {
#if DEBUG > 2
                throw EDGE_DOESNT_EXIST;
#endif
                _exist = false;
            }
#else
            Graph = _Graph;
            edge = _edge;
            x = _x;
            y = _y;
            _exist = true;
#endif
        }

        bool _exist = false;
        _Edge* edge = NULL;
        Static_Graph* Graph;
        unsigned int x, y;

        friend Edge_Iterator;
        friend Vertex;
    };

    //########################################//
    //       KONSTRUKTORY/DESTRUKTORY         //
    //########################################//

    //vertexes - ilosc wierzcholkow w grafie. Nie da sie jej zmienic.
    Static_Graph(unsigned int vertexes_count) {
        graph = new _Edge[vertexes_count * vertexes_count];
        vertexes = new _vertex[vertexes_count];
        vertexscount = vertexes_count;

#ifdef DEBUG_ALLOC_SIZE
        cout << "alloced: " << vertexes_count * vertexes_count * sizeof(_Edge) + vertexes_count * sizeof(_vertex) + sizeof(Static_Graph) << " bytes" << endl;
#endif
    }
    Static_Graph(unsigned int vertexes_count, const VertexType* data, unsigned int vertexes_to_init = vertexes_count) {
#if DEBUG > 1
        if (vertexes_to_init > vertexes_count) {
            throw TO_MUCH_TO_INIT;
        }
#endif
        graph = new _Edge[vertexes_count * vertexes_count];
        vertexes = new _vertex[vertexes_count];
        vertexscount = vertexes_count;

        for (unsigned long int i = 0; i < vertexes_to_init; i++)
        {
            vertexes[i] = _vertex(data[i]);
        }
#ifdef DEBUG_ALLOC_SIZE
        cout << "alloced: " << vertexes_count * vertexes_count * sizeof(_Edge) + vertexes_count * sizeof(_vertex) + sizeof(Static_Graph) << " bytes" << endl;
#endif
    }
    ~Static_Graph() {
        delete[] graph;
        delete[] vertexes;
    }


    //########################################//
    //           FUNKCJE PUBLICZNE            //
    //########################################//


    //Tworzy polaczenie miedzy wierzcholkiem a i b
    void addEdge(unsigned int vertex_a, unsigned int vertex_b, EdgeType edgeprops) {
#if DEBUG > 2
        if (vertex_a > vertexscount || vertex_b > vertexscount) {
            throw VERTEX_DOESNT_EXIST;
        }
#endif
        pos(vertex_a, vertex_b)->connected = true;
        pos(vertex_a, vertex_b)->get_props() = edgeprops;
    }
    //pobiera ilosc wierzcholkow w grafie
    const unsigned int get_vertex_count() const {
        return vertexscount;
    }
    //Pobiera Wierzcholek z grafu
    Vertex get_vertex(unsigned int vertex) {
        return Vertex(*this, vertex);
    }
    //pobiera krawedz z grafu
    Edge get_edge(Vertex from, Vertex to) {
        return Edge(from, to);
    }
    Edge get_edge(unsigned int from, unsigned int to) {
        return Edge(from, to, this);                                            //TUTAJ TODO
    }
    //Szybko pobiera wlasnosc krawedzi
    EdgeType& get_edge_props(unsigned int from, unsigned int to) {
        return pos(from, to).get_props();
    }
    VertexType& get_vertex_props(unsigned int id) {
        return vertexes[id].get_props();
    }
    //drukuje macierz sasiedztwa
    void printconnectionmatrix() {
        for (int i = 0; i < vertexscount; i++)
        {
            for (int j = 0; j < vertexscount; j++)
            {
                cout << get(i, j)->connected << " ";
            }
            cout << endl;
        }
    }

    Static_Graph<VertexType, EdgeType> copy() {
        //TODO
    }
private: //###################################### PRIVATE STUFF ##########################################\\

    //Podklasa definiujaca wierzcholek (lowlevel)
    class _vertex {
    public:
        _vertex() {}
        _vertex(const VertexType& _props) : props(_props) {}
        _vertex(VertexType& _props) : props(_props) {}
        VertexType& get_props() {
            return props;
        }
    private:
        VertexType props;
        friend Vertex;
    };

    //Podklasa definiujaca krawedz (lowlevel)
    class _Edge {
    public:
        bool connected = false;
        _Edge() {

        }
        EdgeType& get_props() {
            return props;
        }
    private:
        EdgeType props;
        friend Edge;
    };


    //lista wierzcholkow. zawiera dane na ich temat
    _vertex* vertexes;
    //macierz sasiedztwa wierzcholkow
    _Edge* graph;
    //ilosc wierzcholkow w grafie
    unsigned int vertexscount;

    //########################################//
    //           FUNKCJE KLASY                //
    //########################################//

    _Edge* pos(unsigned int x, unsigned int y) {
#if DEBUG > 2
        if (x > vertexscount || y > vertexscount) {
            throw POS_ERROR;
        }
#endif
        return (graph + y * vertexscount + x);
    }
    _Edge* get(unsigned int x, unsigned int y) {
#if DEBUG > 2
        if (x > vertexscount || y > vertexscount) {
            throw POS_ERROR;
        }
#endif
        return (graph + y * vertexscount + x);
    }

    friend Edge_Iterator;
    friend Vertex;
    friend Edge;
};

template<typename VertexType, typename EdgeType>
void cout_graph(Static_Graph<VertexType, EdgeType>& G)
{
    cout << "cnt: " << "\t" << "props:" << endl;
    for (int i = 0; i < G.get_vertex_count(); i++)
    {
        auto vertex = G.get_vertex(i);
        for (auto j = vertex.iter_begin(); j < vertex.iter_end(); j++) {
            cout << vertex.get_id() << "->" << (*j).get_neighbor_to().get_id() << " w: " << (*j).get_props().weight << endl;
        }
    }
}
template<typename VertexType, typename EdgeType>
void randomize_graph(Static_Graph<VertexType, EdgeType>& G, float aproximate_fill = 0.5)
{
    unsigned int a, b;
    const unsigned int graph_size = G.get_vertex_count();
    const unsigned int iterations = (unsigned int)(graph_size * graph_size * aproximate_fill);

    for (unsigned int i = 0; i < iterations; i++)
    {
        a = rand() % graph_size;
        b = rand() % graph_size;
        G.addEdge(a, b, EdgeType(rand() % 1000));
    }
}

struct vertex_props {
    vertex_props() {}
    int distance = 0;
    int last = -1;
};
struct edge_props {
    edge_props() : weight(0), num(0) {}
    edge_props(int w) : weight(w), num(0) {}
    edge_props(int w, int n) : weight(w), num(n) {}
    int weight;
    //..
    int num;
};

//WERSJA DLA DYNAMIC GRAPH;

template<
#ifdef USE_VERTEX_DATA
    typename VertexType,
#endif
    typename EdgeType>
void randomize_graph(Dynamic_Graph<
#ifdef USE_VERTEX_DATA
    VertexType,
#endif
    EdgeType>& G, int num_of_edges)
{
    unsigned int a, b;
    const unsigned int graph_size = G.get_vertex_count();
    const unsigned int iterations = num_of_edges;

    for (unsigned int i = 0; i < iterations; i++)
    {
        a = rand() % graph_size;
        b = rand() % graph_size;
        G.addEdge(a, b, EdgeType(rand() % 1000));
    }
}


void DjikstraAlgoritm(
    Dynamic_Graph<edge_props>& graph,
    Dynamic_Graph<edge_props>::Vertex start,
    Dynamic_Graph<edge_props>::Vertex_data<int> & distance,
    Dynamic_Graph<edge_props>::Vertex_data<int>& last)
{
    //funkcja agregacyjna dla set
    struct agg_function {
        agg_function(Dynamic_Graph<edge_props>::Vertex_data<int>& _distance) {
            distance = &_distance;
        }
        bool operator()(unsigned int a, unsigned int b) const {
            return distance->operator()(a) < distance->operator()(b);
        }
        Dynamic_Graph<edge_props>::Vertex_data<int>* distance;
    };

    //Ustaw dis na +inf
    for (int i = 0; i < graph.get_vertex_count(); i++)
    {
        distance(i) = 2000000+i;
    }
    //Ustaw dis w wierzcholek pocz. na 0
    distance(start) = 0;

    //doSprawdzenia <- wszystkie wierzcholki
    auto doSprawdzenia = set<int, agg_function>(agg_function(distance));

    for (int i = 0; i < graph.get_vertex_count(); i++)
    {
        doSprawdzenia.insert(i);
    }

    while (!doSprawdzenia.empty()) {
        //znajdz wierzcholek o najmniejszej wartosci dis (ver)
        auto ver = graph.get_vertex(*(doSprawdzenia.begin()));
        doSprawdzenia.erase(ver.get_id());

        //Dla wszystkich krawedzi wychodzacych od ver i bedacych w doSprawdzenia, wykonaj cos tam
        for (auto i = ver.iter_begin(); i.is_end(); i++)
        {
            if (doSprawdzenia.find(i.get_connection_to_id()) != doSprawdzenia.end()) {
                //cos tam

                auto edge = i.get_edge_props().weight;
                if (distance(i.get_connection_to_id()) > distance(ver.get_id()) + edge) {
                    doSprawdzenia.erase(i.get_connection_to_id());
                    distance(i.get_connection_to_id()) = distance(ver.get_id()) + edge;
                    doSprawdzenia.insert(i.get_connection_to_id());
                    last(i.get_connection_to_id()) = ver.get_id();
                }
            }
        }
    }
}


string get_string_error(ERROR a) {
    switch (a)
    {
    case SUCCESS:
        return "niby dziala";
        break;
    case VERTEX_DOESNT_EXIST:
        return "Krawedz nie istnieje";
        break;
    case VERTEX_FORM_DIFF_GRAPHS:
        return "Wierzchołki należą do różnych grafów";
        break;
    case EDGE_DOESNT_EXIST:
        return "Krawedz nie istnieje";
        break;
    case EDGES_FROM_DIF_GRAPHS:
        return "Krawdznie należą do różnych grafów";
        break;
    case POS_ERROR:
        return "To nie powinno sie wydażyć";
        break;
    case TO_MUCH_TO_INIT:
        return "";
        break;
    default:
        break;
    }
}

#ifdef STATIC
const bool fnc(Static_Graph<vertex_props, edge_props>::Vertex& a, Static_Graph<vertex_props, edge_props>::Vertex& b) {
    return a.get_props().distance > b.get_props().distance;
}
void DjikstraAlgoritm(Static_Graph<vertex_props, edge_props>& graph, Static_Graph<vertex_props, edge_props>::Vertex start) {
    for (int i = 0; i < graph.get_vertex_count(); i++)
    {
        graph.get_vertex(i).get_props().distance = 2000000;
    }
    start.get_props().distance = 0;


    vector<Static_Graph<vertex_props, edge_props>::Vertex> doSprawdzenia;
    doSprawdzenia.resize(graph.get_vertex_count());
    for (int i = 0; i < graph.get_vertex_count(); i++)
    {
        doSprawdzenia[i] = graph.get_vertex(i);;
    }

    while (!doSprawdzenia.empty()) {
        int id = 0, iter = 0;
        auto ver = doSprawdzenia.front();

        for (auto a : doSprawdzenia) {
            if (ver.get_props().distance > a.get_props().distance) {
                ver = a;
                id = iter;
            }
            iter++;
        }

        doSprawdzenia[id] = doSprawdzenia.back();
        doSprawdzenia.pop_back();

        for (auto vertex : doSprawdzenia) {
            if (!vertex.isConnected(ver)) {
                continue;
            }

            auto edge = graph.get_edge(ver, vertex).get_props().weight;
            if (vertex.get_props().distance > ver.get_props().distance + edge) {
                vertex.get_props().distance = ver.get_props().distance + edge;
                vertex.get_props().last = ver.get_id();
            }
        }
    }
}
int main()
{

    Static_Graph<vertex_props, edge_props> graph(5000);

    graph.addEdge(0, 7, edge_props(10));//a->h
    graph.addEdge(0, 4, edge_props(1));//a->e

    graph.addEdge(1, 2, edge_props(2));//b->c

    graph.addEdge(3, 0, edge_props(4));//d->a
    graph.addEdge(3, 7, edge_props(1));//d->h

    graph.addEdge(4, 5, edge_props(3));//e->f

    graph.addEdge(5, 6, edge_props(7));//f->g
    graph.addEdge(5, 8, edge_props(1));//f->i
    graph.addEdge(5, 1, edge_props(1));//f->b
    graph.addEdge(5, 2, edge_props(3));//f->c

    graph.addEdge(7, 8, edge_props(9));//h->i

    graph.addEdge(8, 9, edge_props(2));//i->j

    graph.addEdge(9, 6, edge_props(1));//j->g

    randomize_graph(graph, 0.01);

    //cout_graph(graph);

    //graph.printconnectionmatrix();
    auto vertex1 = graph.get_vertex(6);
    auto vertex2 = graph.get_vertex(9);
    auto edge = graph.get_edge(vertex2, vertex1);

    cout << "Weight: " << edge.get_props().weight << endl;
    cout << "from:" << edge.get_neighbor_form().get_id() << endl;
    cout << "to: " << edge.get_neighbor_to().get_id() << endl;

    cout << endl;

    cout << "All edges from " << vertex1.get_id() << endl;
    for (auto i = vertex1.iter_begin(); i < vertex1.iter_end(); i++)
    {
        cout << (*i).get_props().weight << endl;
    }


    try {
        auto thisdoesntexist = graph.get_vertex(graph.get_vertex_count());
    }
    catch (ERROR a) {
        cout << get_string_error(a) << endl;
    }
    DjikstraAlgoritm(graph, graph.get_vertex(3));
    cout << "Shortest path form 3 to: " << endl;
    for (int i = 0; i < graph.get_vertex_count(); i++)
    {
        if (graph.get_vertex(i).get_props().distance == 2000000) {
            continue;
        }
        cout << i << " " << graph.get_vertex(i).get_props().distance << "\t";
        if (i != 3) {
            int id = graph.get_vertex(i).get_props().last;
            while (id != 3) {
                cout << id << " ";
                id = graph.get_vertex(id).get_props().last;
            }
        }
        cout << endl;
    }

    getchar();
}
#else
int main()
{

    //Losowy graf z 40000 wierzcholkami i 300000 krawedziami

    Dynamic_Graph<edge_props> graph(10);

    graph.addEdge(0, 7, edge_props(10));//a->h
    graph.addEdge(0, 4, edge_props(1));//a->e

    graph.addEdge(1, 2, edge_props(2));//b->c

    graph.addEdge(3, 0, edge_props(4));//d->a
    graph.addEdge(3, 7, edge_props(1));//d->h

    graph.addEdge(4, 5, edge_props(3));//e->f

    graph.addEdge(5, 6, edge_props(7));//f->g
    graph.addEdge(5, 8, edge_props(1));//f->i
    graph.addEdge(5, 1, edge_props(1));//f->b
    graph.addEdge(5, 2, edge_props(3));//f->c

    graph.addEdge(7, 8, edge_props(9));//h->i

    graph.addEdge(8, 9, edge_props(2));//i->j

    graph.addEdge(9, 6, edge_props(1));//j->g

    //randomize_graph(graph, 300000);

    auto vertex = graph.get_vertex(0);
    auto vertex1 = graph.get_vertex(5);
    auto vertex2 = graph.get_vertex(4);
    auto edge = graph.get_edge(vertex2, vertex1);

    cout << "Weight: " << edge.get_props().weight << endl;
    cout << "from:" << edge.get_vertex_from().get_id() << endl;
    cout << "to: " << edge.get_vertex_to().get_id() << endl;

    cout << endl;

    cout << "All edges from " << vertex1.get_id() << endl;
    for (auto i = vertex1.iter_begin(); i.is_end(); i++)
    {
        cout << (*i).get_props().weight << endl;
    }


//#define PRINT_THIS_SHIT //(drukuje wszystkie wierzchokli)
#ifdef PRINT_THIS_SHIT
    for (int j = 0; j < graph.get_vetrex_count(); j++)
    {
        for (auto i = graph.get_vertex(j).iter_begin(); i.is_end(); i++) {
            cout << j << " " << i.get_connection_to_id() << " " << (*i).get_props().weight << endl;
        }
    }
#endif
    int target = 3;
    auto distance = graph.create_vertex_data<int>();
    auto last = graph.create_vertex_data<int>();
    DjikstraAlgoritm(graph, graph.get_vertex(target),distance,last);
    cout << endl;
    cout << distance << endl << endl;

    for (int i = 0; i < distance.get_size(); i++)
    {
        cout << distance(i) << "\t" << i << " ";
        if (i != target) {
            auto id = last(i);
            while (id != target) {
                cout << id << " ";
                id = last(id);
            }
        }
        cout << target << endl;
    }
    getchar();
}
#endif