uva534

結果是用prim算出來

不知道用dijkstra要怎麼算（雖然prim原本就跟dijkstra長得很像）

並意外發現了，primｎ算法可以解決
Ａ點到Ｂ點，其中路徑上的權重“最大值是最小的”

題目的這一點，困擾了我許久

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <float.h>
#include <math.h>
#include <string>
#include <string.h>
using namespace std;
typedef struct NO{
    int id;
    double x;
    double y;
}no;

bool visited[201];
double d[201];
int parent[201];
no r[201];

double dis(int a,int b){
    double x=r[a].x-r[b].x;
    double y=r[a].y-r[b].y;

    //printf("source:%d destination:%d sqrt:%0.3lf\n",a,b,sqrt(x*x+y*y));
    return sqrt(x*x+y*y);

}


int main(){
    int a;
    double b,c;
    int in;
    int num_r;
    int index=1;
    while(1){
        scanf("%d",&a);
        if(a==0) break;
        in = 0;
        while(a--){
            scanf("%lf %lf",&b,&c);
            r[in].x=b;
            r[in].y=c;
            in++;
        }
        num_r=in;

        for(int i=0;i<num_r;i++){
            d[i]=DBL_MAX;
        }
        memset(visited,0,sizeof(visited));
        memset(parent,0,sizeof(parent));

        d[0]=0;
        parent[0]=0;
        for(int j=0;j<num_r;j++){
            int e=-1;
            double min=DBL_MAX;
            int temp;
            for(int i=0;i<num_r;i++){
                if(!visited[i] && d[i]<min){
                    min=d[i];
                    e=i;
                }
            }
            if(e==-1) break;
            visited[e]=true;
            for(int i=0;i<num_r;i++){
                if(!visited[i] && dis(e,i)<d[i]){
                    d[i]=dis(e,i);
                    parent[i]=e;
                }
            }
        }
        double max=DBL_MIN;
        for(int i=1;i!=0;i=parent[i]){
            //printf("d[i]:%lf",d[i]);
            if(d[i]>max){
                max=d[i];
            }
        }
        printf("Scenario #%d\n",index++);
        printf("Frog Distance = %0.3lf\n",max);
        printf("\n");
    }


    return 0;
}