OJ Board

Code: Select all

// Q534  Frogger 
// select the minimum of longest jumps ~~ minimax

#include<iostream>
#include<cstdlib>
#include<stdio.h>
#include<math.h>
#define MAX 201

using namespace std;

int n, index = 1;
double d[MAX][MAX], ar[MAX][2];

void Floyed_Warshall();
int min(int a, int b);
int max(int a, int b);

int main(int argc, char argv[])
{
    while(cin >> n)
    {
        if(n == 0)
            break;
                
        for(int i = 1; i <= n; i++)
            cin >> ar[i][0] >> ar[i][1];
        
        for(int i = 1; i <= n; i++)
            for(int j = i+1; j <= n; j++)
                d[j][i] = d[i][j] = 
                sqrt((ar[j][1]-ar[i][1])*(ar[j][1]-ar[i][1])+(ar[j][0]-ar[i][0])*(ar[j][0]-ar[i][0]));
                
        Floyed_Warshall();
        cout << "Scenario #" << index++ << endl << "Frog Distance = ";
        printf("%.3f\n\n",d[1][2]);
    }
    system("PAUSE");
    return EXIT_SUCCESS;
}

void Floyed_Warshall()
{
     for(int i = 1; i <= n; i++)
            d[i][i] = 0;
        
     for(int k = 1; k <= n; k++)
         for(int i = 1; i <= n; i++)
             for (int j = 1; j <= n; j++)
                 d[i][j] = min(d[i][j], max(d[i][k], d[k][j]));
}

int min(int a, int b)
{
    return (a < b) ? a: b;
}

int max(int a, int b)
{
    return (a > b) ? a: b;
}

Code: Select all

#include<cstdio>
#include<cmath>
#include<memory>
	int min(int a,int b)
		{
			if(a>b)
				return b;
			else
				return a;
		}
	int max(int a,int b)
		{
			if(a>b)
				return a;
			else
				return b;
		}
	int main()
		{

			int  graph[300][300],x[300],y[300],v=1;
			int n,i,j,k,k1,k2;
			while(scanf("%d",&n) && n)
			 {
			
				for(i=0;i<n;i++)
					scanf("%d%d",&x[i],&y[i]);
				for(i=0;i<n;i++)
				  {
					for(j=i;j<n;j++)
					   {
					     graph[i][j]=graph[j][i]=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
					   }  

				 }
				/*for(i=0;i<n;i++)
				 {
					for(j=0;j<n;j++)
						printf("%d ",graph[i][j]);
					printf("\n");
				}*/
				for(k=0;k<n;k++)
				 {
				    for(i=0;i<n;i++)
					{
				          for(j=0;j<n;j++)
						{
							k1=max(graph[i][k],graph[k][j]);
							k2=graph[i][j];
							graph[i][j]=min(k1,k2);
						}
					}
				}
			printf("Scenario #%d\n",v++);
			printf("Frog Distance = %.3lf\n",sqrt((double)graph[0][1]));
			 }
		}

Code: Select all

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define Node_num 210004

struct S
{
	int u,v,cost;
};
S a[Node_num];

int Set[Node_num],Rank[Node_num];
int Node,Edge;
int x[210003],y[210003];

void make_set(int x)
{
	Set[x] = x;
	Rank[x] = 0;
}

int find_set(int x)
{
	if(x != Set[x])
	{
		Set[x] = find_set(Set[x]);
	}
	return Set[x];
}

void Union(int x,int y)
{
	if(Rank[x] > Rank[y])
	{
		Set[y] = x;
	}
	else
	{
		Set[x] = y;
		if(Rank[x] == Rank[y])
		{
			Rank[y]++;
		}
	}
	return;
}

int comp_fun(const void *m,const void *n)
{
	S *x,*y;
	x=(S*)m;
	y=(S*)n;
	return ( x->cost - y->cost );
}

int main()
{
	int  test,n,m,s,k,i,j,t1,t2,u_set,v_set,kase=1,mn;
	double sum;

	while(scanf("%d",&n) == 1 && n)
	{
		for(i=0;i<n;i++)
			scanf("%d %d",&x[i],&y[i]);

		k=0;
		for(i=0;i<n-1;i++)
		{
			for(j=i+1;j<n;j++)
            {

                a[k].u=i,a[k].v=j;
                t1=x[i]-x[j];t2=y[i]-y[j];
                a[k].cost = t1*t1 + t2*t2;
                k++;
            }
		}

		qsort(a,k,sizeof(S),comp_fun);

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

		for(i=0; i<k ;i++)
		{
			u_set=find_set(0);
			v_set=find_set(1);
			if(u_set != v_set)
			{
				Union(a[i].u,a[i].v);
			}
			else break;
		}
		if(i==0)i = 1;
		sum = sqrt(a[i-1].cost);
		printf("Scenario #%d\nFrog Distance = %.3lf\n\n",kase++,sum);
	}
	return 0;
}
[list]IMPOSSIBLE MEANS I M POSSIBLE [/list]

Code: Select all

#include<iostream>
#include<cstdio>
#include<vector>
#include<cmath>
#define sz 205
#define inf 9999
using namespace std;

vector<long long>myVec[sz];
vector<double>dst[sz];

double findPath(long long r, long long pr[], double st[][sz], double mn)
{
    
	if(pr[r] == r)
    {
        printf("Frog Distance = %.3lf\n\n", mn);
		return 0;
    }

	else
	{
	    if(mn < st[r][pr[r]])
            mn = st[r][pr[r]];
        
		findPath(pr[r], pr, st, mn);
	}
}

long long shortestPath(long long n, long long from, long long to)
{
    long long hold, index, pr[sz], visit[sz];
    double mn, newDist, d[sz], st[sz][sz];

    for(long long i=0;i<=n;i++)
    {
        pr[i] = i;
        d[i] = inf;
        visit[i] = 0;
    }

    d[from] = 0;
    visit[from] = 1;

    while(from != to)
    {
        for(long long i=0;i<myVec[from].size();i++)
        {
            index = myVec[from][i];

            if(visit[index] == 0)
            {
                newDist = dst[from][i];
                if(newDist < d[index])
                {
                    pr[index] = from;
                    d[index] = newDist;
                }
            }
        }

        mn = inf;
        for(long long i=0;i<=n;i++)
        {
            if(visit[i] == 0 && d[i] < mn)
            {
                mn = d[i];
                hold = i;
            }
        }
        
        st[hold][from] = mn;
        from = hold;
        visit[from] = 1;
    }
    
    mn = 0;
    findPath(to, pr, st, mn);

    return 0;
}

int main()
{
    long long n, T=1;
    double dist, pos[sz][2];

    while(cin>>n)
    {
        if(n==0)
            break;

        for(long long i=1;i<=n;i++)
            cin>>pos[i][0]>>pos[i][1];

        for(long long i=1;i<=n-1;i++)
        {
            for(long long j=i+1;j<=n;j++)
            {
                dist = sqrt(pow((pos[i][0] - pos[j][0]), 2) + pow((pos[i][1] - pos[j][1]), 2));
                myVec[i].push_back(j);
                myVec[j].push_back(i);
                dst[i].push_back(dist);
                dst[j].push_back(dist);
            }
        }

        cout<<"Scenario #"<<T++<<endl;
        shortestPath(n, 2, 1);

        for(long long i=0;i<=n;i++)
        {
            myVec[i].clear();
            dst[i].clear();
        }
    }
    return 0;
}