ASDps3

#include <iostream>
#include <fstream>
using namespace std;
class Dijkstra
{
    public:
    int**przed;//macierz incydencji dla pierwotnego układu dróg
    int**po;//macierz incydencji po wstawieniu drogi
    int**poten;//macierz zawierajaca informacje o kolejnych mozliwych drogach do wstawienia
    int**dijkstra;//macierz wykonywania operacji algorytmu dijkstry
    int **dlugosc;//wektor pokazujący wartosci dlugosci minimalnych drog
    int miasta;
    int trakty;
    int dozb;
    Dijkstra()
    {

        //odczyt z pliku
        cout<<"wczytuje dane z pliku"<<endl;
        ifstream F;
        F.open("in.txt");
        //tworz dynamiczne macierze
        F>>miasta;F>>trakty;F>>dozb;
        //macierz dla algorytmu
        dijkstra = new int *[miasta];
        for(int i=0;i<miasta;i++)
        {
            dijkstra[i]= new int[miasta];
        }
        //wektory rozwiazan algorytmu
        dlugosc = new int *[2];
        for(int i=0;i<miasta;i++)
        {
            dlugosc[i]= new int[miasta];
        }
        //macierz dla dijkstry przed
        przed = new int *[miasta];
        for(int i=0;i<miasta;i++)
        {
            przed[i]= new int[miasta];
        }
        //macierz dla dijkstry po
        po = new int *[miasta];
        for(int i=0;i<miasta;i++)
        {
            po[i]= new int[miasta];
        }
        int temp=0;
        int pocz=0;
        int kon=0;
        temp=trakty;
        //macierz dla krawedzi potencjalnych do zbudowania,charakterystyka listowa
        poten=new int *[3];
        for (int j=0;j<3;j++)
            {
                poten[j]=new int[trakty];
            }
        //wstepny brak krawedzi w grafie przed tzn.-1
        for(int i=0;i<miasta;i++)
        {
            for(int j=0;j<miasta;j++)
            {
                przed[i][j]=-1;
                cout<<przed[i][j];
            }
        }
        //wierzchołki,nadpisanie na 0
        for(int i=0;i<miasta;i++)
        {
            przed[i][i]=0;
            cout<<"c";
        }
        for(int i=temp;i>0;i--)
        {
            F>>pocz;
            F>>kon;
            F>>przed[pocz-1][kon-1];
            cout<<i<<" ";
        }
        cout<<"b";
        //symetryzacja
        for(int i=0;i<miasta;i++)
        {
            for(int j=0;j<miasta;j++)
            {
                if(przed[i][j]!=0 && przed[i][j]!=-1)
                {
                    przed[j][i]=przed[i][j];
                }
            }
        }
        //skopiuj macierz przed na po
        for(int i=0;i<miasta;i++)
        {
            for(int j=0;j<miasta;j++)
            {
                po[i][j]=przed[i][j];
            }
        }
        for(int i=0;i<trakty;i++)
        {
            cout<<i<<" ";
            F>>poten[0][i];
            F>>poten[1][i];
            F>>poten[2][i];
        }
        F.close();
        //wyswietl zawartosc macierzy przed
        cout<<"zawartosc macierzy przed"<<endl;
        for(int i=0;i<miasta;i++)
        {
            for(int j=0;j<miasta;j++)
            {
                cout<<przed[i][j]<<" ";
            }
            cout<<endl;
        }
        //wyswietl zawartosc macierzy po
        cout<<"zawartosc macierzy po"<<endl;
        for(int i=0;i<miasta;i++)
        {
            for(int j=0;j<miasta;j++)
            {
                cout<<po[i][j]<<" ";
            }
            cout<<endl;
        }
        cout<<"zawartosc macierzy potencjalnej"<<endl;
    }
    void przywroc_po()
    {
        for(int i=0;i<miasta;i++)
        {
            for(int j=0;j<miasta;j++)
            {
                po[i][j]=przed[i][j];
            }
        }
    }
    void wysw_po()
    {
        cout<<"nowa macierz po"<<endl<<endl;
        for(int i=0;i<miasta;i++)
        {
            for(int j=0;j<miasta;j++)
            {
                cout<<po[i][j]<<" ";
            }
            cout<<endl;
        }
    }
    class Dixtra{
        public:
        int* odl;//odleglosci aktualne
        int* pop;//poprawione odleglosci po odwiedzeniu kolejnego miasta
        bool* odw;//miasta odwiedzone

    };
    int* dixtra(int** odleglosci){
        Dixtra dix;
        dix.odl=new int[miasta];
        dix.pop=new int[miasta];
        dix.odw=new bool[miasta];
            dix.odl[0]=0;
            dix.pop[0]=0;
            dix.odw[0]=true;
        for(int i=1;i<miasta;i++)
        {
            dix.odl[i]=odleglosci[0][i];
            dix.pop[i]=-1;
            dix.odw[i]=false;
        }
        for(int i=1,min_odl,min_wie;i<miasta-1;i++)
        {
            min_odl =-1;
            min_wie =-1;
            bool znalazl_nieodwiedzone_miasto=false;
            for(int j=0;j<miasta-1;j++){
                if(dix.odw[j]==false && dix.odl[j]!=-1){
                    if(znalazl_nieodwiedzone_miasto){
                        min_odl = dix.odl[j];
                        min_wie = j;
                    }
                    else if(dix.odl[j]<min_odl){
                        min_odl = dix.odl[j];
                        min_wie = j;
                    }
                }
            }
            if(min_wie==-1 || min_wie>miasta){
                continue;
            }
            for(int j=1;j<miasta-1;j++){
                if(odleglosci[min_wie][j]+dix.odl[min_wie]<dix.odl[j]){
                    dix.pop[j]=odleglosci[min_wie][j]+dix.odl[min_wie];
                }
                else{
                    dix.pop[j]=dix.odl[j];
                }
            }
            for(int j=1;j<miasta-1;j++){
                dix.odl[j]=dix.pop[j];
            }
            dix.odw[min_wie]=true;
        }
        return dix.odl;
    }
    void algorytm()
    {
        ofstream ofs("out.txt");
        int suma;
        int* odleglosci_przed = dixtra(przed);

        for(int t=0;t<trakty;t++){
            suma=0;
            for(int i=0;i<miasta;i++)
            {
                for(int j=0;j<miasta;j++)
                {
                    po[i][j]=przed[i][j];
                }
            }
            po[poten[0][t]][poten[1][t]]=poten[2][t];
            po[poten[1][t]][poten[0][t]]=poten[2][t];
            int* odleglosci_po = dixtra(po);
            for(int i=0;i<miasta;i++)
            {
                if(odleglosci_po<odleglosci_przed){
                    suma++;
                }
            }
            ofs<<suma<<endl;

        }

        /*
        int *dystans;//szukanie minimum
        dystans = new int [miasta];
        int *min;
        min = new int [miasta];
        przed[0][1];
        suma = new int[miasta];
        //rozpoczynamy od pierwszego wiersza macierzy incydencji
        for(int i=0;i<miasta;i++)
        {
            dijkstra[0][i]=przed[0][i];
            //dystans 1->1 =0
            dijkstra[i][0]=0;
        }
        if(przed[i][]>0 && min
        */
    }



    ~Dijkstra()
    {
        cout<<"usuwam"<<endl;
        delete [] przed;
        cout<<"usunalem"<<endl;
        delete [] po;
        cout<<"usunieto"<<endl;
        delete [] dijkstra;
        cout<<"usunieto"<<endl;
        delete [] dlugosc;
        cout<<"usunieto"<<endl;
    }
};
int main()
{
        Dijkstra a;
        a.algorytm();
        system("PAUSE");
        return 0;
}