1174 - Commandos

Problem Link : http://lightoj.com/volume_showproblem.php?problem=1174

Solution:

#include<bits/stdc++.h>
#define inf 1000000

using namespace std;


int dis [101][101];


int main()
{


    int n,e,t;
    int a,b,c;
    int s,d,w;

    scanf("%d",&t);

    for(int ca=1; ca<=t; ca++)
    {

        scanf("%d%d",&n,&e);

        for(int i=0; i<n; i++)
        {
            for(int j=0; j<n; j++)
            {
                if (i==j)
                {
                    dis[i][j]=0;
                }
                else
                {
                    dis[i][j]=inf;
                }
            }
        }





        for(int i=0; i<e; i++)
        {
            scanf("%d%d",&a,&b);

            dis[a][b]=1;
            dis[b][a]=1;


        }

        for(int k=0; k<n; k++)

            for(int i=0; i<n; i++)

                for(int j=0; j<n; j++)
                {
                    if(dis[i][j]>dis[i][k]+dis[k][j])
                    {
                        dis[i][j]=dis[i][k]+dis[k][j];

                    }
                }


        w=1;
        if(e==0) w=0;
        scanf("%d%d",&s,&d);

        for(int i=0; i<n; i++)
        {
            if(s!=i and d!=i) w=max(w,dis[s][i]+dis[i][d]);
        }



        printf("Case %d: %d\n",ca,w);
    }
}