UVA 534 - Frogger(cpp file)

Problem Type : MST + floyd Warshall


Code :


#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#define MAX 201
using namespace std;
double arr[MAX][MAX];


int main()
{
    int i,j,k,len,x[MAX],y[MAX],node,cou=0;
    double px,py,ux;
    while(scanf("%d",&node)&&node)
    {
        cou++;
        for ( int i = 0; i < node; i++ )
        {
            scanf ("%d %d", &x [i], &y [i]);
        }
        for(i=0; i<node; i++)
        {
            for(j=i+1; j<=node; j++)
            {
                px=pow((x[i]-x[j]),2);
                py=pow((y[i]-y[j]),2);
                ux=sqrt(px+py);
                arr[i][j]=arr[j][i]=ux;
            }
        }
        for(k=0; k<node; k++)
        {
            for(i=0; i<node; i++)
            {
                for(j=0; j<node; j++)
                {
                    if(arr[i][j]!=0 && arr[i][k]>0 && arr[k][j]>0)
                    {
                        arr[i][j]=min(arr[i][j],max(arr[i][k],arr[k][j]));
                    }
                }
            }
        }
        printf("Scenario #%d\n",cou);
        printf("Frog Distance = %.3lf\n\n",arr[0][1]);
        memset(arr,0,sizeof(arr));
        memset(x,0,sizeof(x));
        memset(y,0,sizeof(y));
    }

}