#include <iostream>
#include <fstream>
#include <set>
#include <utility>

using namespace std;

int main()
{

     set< pair<int,int> > pereche;
     set< pair<int,int> >::iterator it;
     pair<int,int>p;
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");
    int n, *d, *t, inc, poz,fin,**m;
    f>>n;
    d=new int[n+1];
    t=new int[n+1];
    m=new int*[n+1];
    for(int i=1;i<=n;i++)
        m[i]=new int[n+1];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            f>>m[i][j];
    f>>inc;
    for(int i=1;i<=n;i++)
    {
        p=make_pair(m[inc][i],i);
        pereche.insert(p);
        t[i]=0;
        d[i]=0;
    }

    f>>fin;
    for(int i=1;i<=n;i++)
        {
            d[i]=m[inc][i];
            if(i!=inc)
                t[i]=inc;
        }

    pereche.erase(pereche.begin());
    while (!pereche.empty())
    {
        poz=(*pereche.begin()).second;
        for(int i=1;i<=n;i++)
            if(d[i]>d[poz]+m[poz][i])
        {
            p=make_pair(d[i],i);
            d[i]=d[poz]+m[poz][i];

            it=pereche.find(p);
            pereche.erase (it);
            p=make_pair(d[i],i);
            pereche.insert(p);
            t[i]=poz;
        }
        pereche.erase(pereche.begin());
    }
    cout<<"Vectorul de cost:"<<endl;
    for(int i=1;i<=n;i++)
        cout<<d[i]<<" ";
    cout<<endl<<"Vectorul de tati:"<<endl;
    for(int i=1;i<=n;i++)
        cout<<t[i]<<" ";
    cout<<"\nDrumul pana la nodul "<<fin<<" are costul "<<d[fin]<<" si este compus din nodurile: ";
    int i=fin;
    while(i!=inc)
    {
        cout<<t[i]<<" ";
        i=t[i];
    }
    return 0;
}