pku 2253 迪结斯特拉变种.txt

ACM资料大集合

#include <stdio.h>
#include <iostream>
#include <math.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;

//PKU 2253 迪结斯特拉变种 
#define NMAX 205
#define INFI 99999999 

typedef struct ooppoint
{
 int x;
 int y;
}ooppoint;

ooppoint point[NMAX];
int cost[NMAX][NMAX];
int fun[NMAX]; 
bool visited[NMAX]; 
void init(int num)
{
     int i,j;
     for(i=1;i<=num;i++)
     {
      for(j=1;j<=num;j++)
      cost[i][j]=(point[i].x-point[j].x)*(point[i].x-point[j].x)+
      (point[i].y-point[j].y)*(point[i].y-point[j].y);
      cost[i][i]=INFI;
     }
}

void print_fun(int num)
{
     int i;
     for(i=1;i<=num;i++)
     printf("%d ",fun[i]);
     printf("\n"); 
} 

int getmax(int a,int b)
{
    if(a<b) return b;
    else return a; 
} 
void dzs(int num,int start,int end)
{
 int i,j,min,minnum;
 for(i=1;i<=num;i++)  
 {
   fun[i]=cost[start][i];
   visited[i]=false; 
 }
 visited[start]=true;
//  print_fun(num);
 for(i=1;i<num-1;i++)
 {
   min=INFI;
   for(j=1;j<=num;j++)
   {
       if(visited[j]==false)
       {
           if(fun[j]<min)
            {
               minnum=j;
               min=fun[j]; 
             } 
       }
   } 
   visited[minnum]=true;
 //  printf("minnum=%d\n",minnum); 
   for(j=1;j<=num;j++)
   {//注意if的条件，fun[j]取的是fun[minnum]和cost[j][minnum]的较大值 
    if(visited[j]==false && fun[j]>getmax(fun[minnum],cost[j][minnum])) 
    fun[j]=getmax(fun[minnum],cost[j][minnum]); 
   }
//   print_fun(num); 
 }
 printf("Frog Distance = %.3lf\n\n",sqrt((double)(fun[end]))); 
}

int main()
{
 int num,i,j;
 scanf("%d",&num);
 j=0; 
 while(num!=0)
 { 
  for(i=1;i<=num;i++)
   {
    scanf("%d %d",&point[i].x,&point[i].y); 
 //   printf("%d\n",point[i].x); 
    }
    init(num);
    printf("Scenario #%d\n",++j); 
    dzs(num,1,2); 
    scanf("%d",&num); 
 }   
 return 0;    
}