567 - Risk uva solution

 // pure floyed warshal


#include<bits/stdc++.h>
using namespace std;
int g[40][40];
int n,m,test;


void ini()
{
    for(int i=0;i<20;i++)
        for(int j=0;j<20;j++)
        {
            if(i==j)
                g[i][j]=0;
            else
                g[i][j]=10000;
        }

}
void floyed_warshal()
{
    int i,j,k;
    for(k=0;k<20;k++)
        {
            for(i=0;i<20;i++)
            {
                for(j=0;j<20;j++)
                {
                    g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
                }
            }
        }
}
void printtestset()
{
    int a,b;
    cin>>test;
    for(int k=0;k<test;k++)
    {

        cin>>a>>b;

        printf("%2d to %2d: %d\n",a,b,g[a-1][b-1]);
    }

}


void printpath()
{
    for(int i=0;i<5;i++)
    {
        for(int j=0;j<5;j++)
        {
            cout<<g[i][j]<<"  ";
        }
        cout<<endl;
    }
}

int main()
{
    for(int t=1; ;t++)
    {
        ini();
        for(int i=0;i<19;i++)
        {
            if(scanf("%d",&m)==-1) return 0;

            for(int j=0;j<m;j++)
            {
                cin>>n;
                g[i][n-1]=1;
                g[n-1][i]=1;
            }


        }
        floyed_warshal();
        //printpath();
        cout<<"Test Set #"<<t<<endl;
        printtestset();
        cout<<endl;
    }


    return 0;
}

SHARE

Amit Ghosh

• 
• 
• 
• 
•