#include <cstdlib>

using namespace std;

 struct Graf
{
    Graf( int pocetVrcholu, int pocetHran );
    
    int pocetVrcholu();
    
    void vlozHranu( int vrchol1, int vrchol2, double vaha );
    
    int pocetSousedu( int vrchol );
    
    /***
     * Vraci sousedni vrchol a vahu hrany
     */
    int nactiSouseda( int vrchol, int indexSouseda, double* vahaHrany );
};

enum StavVrcholu{ znamy, pokusny, neznamy };

void Dijkstra( Graf* graf, int start, int cil,
               int* cesta,
               int* pocetVrcholuCesty,
               double* delkaCesty ) 
{
    /****
     * Inicializace pomocnych poli
     */
    int pocetVrcholu = graf->pocetVrcholu();
    double * cestaDoVrcholu = new double [ pocetVrcholu ];    
    for (int i=0; i < pocetVrcholu; i++)
        cestaDoVrcholu[i] = DBL_MAX;
    cestaDoVrcholu[start] = 0;    
    StavVrcholu* stavyVrcholu = new StavVrcholu[ pocetVrcholu ];
    for (int i=0; i < pocetVrcholu; i++)
        stavyVrcholu[i] = neznamy;
    stavyVrcholu[ start] = znamy;                          
    
    /****
     * Vypocet nejkratsich cest do jednotlivych vrcholu
     */
    double vahaHrany = 0;
    int nejblizsiVrchol = start;
    while(stavyVrcholu[cil]!=znamy)
    {
        /****
         * Prepocet hodnot v sousedech
         */
        for(int i=0; i<graf->pocetSousedu(nejblizsiVrchol);i++)
        {
            
            int soused = graf->nactiSouseda(nejblizsiVrchol, i, &vahaHrany);
            if(stavyVrcholu[soused] == znamy)
                continue;
            double cestaDoSouseda = cestaDoVrcholu[nejblizsiVrchol]+vahaHrany;
            if(cestaDoSouseda<cestaDoVrcholu[soused])
            cestaDoVrcholu[soused] = cestaDoSouseda;
            stavyVrcholu[soused] = pokusny;
        }
        
        /****
         * Nalezeni nejmensiho pokusnehos
         */
        double nejmensi = DBL_MAX;
        for(int i = 0; i< pocetVrcholu; i++)
        {
            if(stavyVrcholu[i] == znamy)
                continue;
            if(cestaDoVrcholu[i] < nejmensi)
            {
                nejmensi = cestaDoVrcholu[i];
                nejblizsiVrchol = i;
            }
        }
        stavyVrcholu[nejblizsiVrchol] = znamy;
    }
    
    /****
     * Rekonstrukce nejkratsi cesty
     */
    delkaCesty = cestaDoVrcholu[cil];
    int vrchol = cil;
    *pocetVrcholuCesty = 1;
    cesta[0] = cil;
    while( vrchol != start )
    {
        for( int i = 0;graf->pocetSousedu( vrchol ); i++ )
        {
            int soused = graf->nactiSouseda( vrchol, i, vahaHrany );
            if( cestaDoVrcholu[ vrchol ] - cestaDoVrcholu[ soused ] == vahaHrany )
            {
                cesta[*pocetVrcholuCesty] = soused;
                vrchol = soused;
                *pocetVrcholuCesty++;
                break;
            }
        }
    }
    
    /****
     * Prevraceni poradi vrcholu nejkratsi cesty
     */
    int i = 0;
    int j = pocetVrcholuCesty - 1;
    while( i < j )
    {
        int pomocna = cesta[ i ];
        cesta[ i ] = cesta[ j ];
        cesta[ j ] = pomocna;
        i++;
        j--;
    }
    
    /****
     * Dealokace pomocnych poli
     */
    delete[] cestaDoVrcholu;
    delete[] stavyVrcholu;
}

int main(int argc, char** argv)
{

    return 0;
}