drum

#include<bits/stdc++.h>
using namespace std;
ifstream fin("drum.in");
ofstream fout("drum.out");
int a[1001][1001], l[1001][1001], n, numar;
int drum(int i, int j)
{
    int ok=0, k;
    for(k=1; k<=n && ok==0; k++)
    {
        if(a[i][j]==a[i][k]+a[k][j] && k!=i && k!=j)
        {
            ok=1;
            drum(i, k);
            drum(k, j);
        }
    }
    if(ok==0)
    {
        a[numar][j]=l[numar][j];
    }
}
void scrie(int inf)
{
    fout<<inf;
    int i, j;
    for(i=1; i<=n; i++)
    {
        for(j=1; j<=n; j++)
        {
            cout<<a[i][j]<<' ';
        }
        cout<<endl;
    }
}
int roy_floyd()
{
    int k, i, j;
    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];
                    l[i][j]=l[i][k]+l[k][j];
                }
            }
        }
    }
}
int main()
{
    int i, j, k, inf;
    fin>>n;
    memset(a, 10, sizeof(a));
    inf=a[0][0];
    while(fin>>i>>j)
    {
        a[i][j]=1;
        l[i][j]=1;
    }
    for(k=1; k<=n; k++)
    {
        a[k][k]=0;
    }
    roy_floyd();
    for(i=1; i<=n; i++)
    {
        for(j=1; j<=n; j++)
        {
            if(a[i][j]!=0 && a[i][j]!=inf)
            {
                numar=i;
             //   cout<<i<<' ';
                drum(i, j);
                //cout<<endl;
            }
        }
    }
    scrie(inf);

}







#include<bits/stdc++.h>
using namespace std;
ifstream fin("drum.in");
ofstream fout("drum.out");
int a[1001][1001], l[1001][1001], n, numar;
int drum(int i, int j)
{
    int ok=0, k;
    for(k=1; k<=n && ok==0; k++)
    {
        if(a[i][j]==a[i][k]+a[k][j] && k!=i && k!=j)
        {
            ok=1;
            drum(i, k);
            drum(k, j);
        }
    }
    if(ok==0)
    {
        a[numar][j]=l[numar][j];
    }
}
void scrie(int inf)
{
    fout<<inf;
    int i, j;
    for(i=1; i<=n; i++)
    {
        for(j=1; j<=n; j++)
        {
            cout<<a[i][j]<<' ';
        }
        cout<<endl;
    }
}
int roy_floyd()
{
    int k, i, j;
    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];
                    l[i][j]=l[i][k]+l[k][j];
                }
            }
        }
    }
}
int main()
{
    int i, j, k, inf;
    fin>>n;
    memset(a, 10, sizeof(a));
    inf=a[0][0];
    while(fin>>i>>j)
    {
        a[i][j]=1;
        l[i][j]=1;
    }
    for(k=1; k<=n; k++)
    {
        a[k][k]=0;
    }
    roy_floyd();
    for(i=1; i<=n; i++)
    {
        for(j=1; j<=n; j++)
        {
            if(a[i][j]!=0 && a[i][j]!=inf)
            {
                numar=i;
             //   cout<<i<<' ';
                drum(i, j);
                //cout<<endl;
            }
        }
    }
    scrie(inf);

}