Prob 3

#include <bits/stdc++.h>
# define NMAX 50000
using namespace std;

int n, a[105][105],p,q,m[100][100];

void Read()
{
    ifstream fin("date.in");
    int i, j;
    fin >>n>>p>>q;

    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
            fin >> m[i][j];
    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
            fin >> a[i][j];

}


void Roy_Floyd()
{
    int i, j, k;
    for (k = 1; k <= n; k++)
        for (i = 1; i <= n; i++)
            for (j = 1; j <= n; j++)
                if (a[i][j] > a[i][k] + a[k][j])
                    a[i][j] = a[i][k] + a[k][j];
}
void drum(int i,int j)
{
    int k,gasit;
    for(k=1,gasit=0;k<=n && !gasit;k++)
    if(i!=k && j!=k && a[i][j]==a[i][k]+a[k][j])
    {
        drum(i,k);
        drum(k,j);
        gasit=1;
        }
     if(!gasit)
     cout<<j<<" ";
}


//void Write()
//{
//  int i, j;
//  for (i = 1; i <= n; i++)
//  {
//      for (j = 1; j <= n; j++)
//        cout << a[i][j]<<" ";
//      cout << endl;
//  }
//}


int main()
{
    Read();
    if(m[p][q]==1)
        cout<<"Da";
    else
        cout<<"Nu";
    cout<<endl;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(m[i][j]==1)
                {
                    cout<<i<<" si "<<j<<" "<<a[i][j]<<" ";
                    cout<<endl;
                }
    Roy_Floyd();
    cout<<4<<":";
    drum(4,1);
   // Write();
    return 0;
}