View Code of Problem 1315

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = 220;
double dis[maxn]; ///到各点的距离
bool used[maxn]; ///标记该点是否已经使用
//int pre[maxn]; ///最短路经过的路径
double map[maxn][maxn];
int n;
struct Node
{
    int x,y;
} node[maxn];
void dijkstra(){
//	memset(used,false,sizeof used);
	for(int i=1;i<=n;i++){
		dis[i] = map[1][i];
		used[i] = false;
//		pre[i] = (dis[i]==INF)?-1:a;
	}
//	dis[1] = 0;
//	used[1] = true;
	for(int i=1;i<=n;i++){
		double Min = INF;
		int Np = -1;
		for(int j=1;j<=n;j++)
			if(!used[j] && dis[j] <=Min){
				Np = j;
				Min = dis[j];
			}
		if(Np == -1)
			return;
		used[Np] = true;
		for(int j=1;j<=n;j++)
			if(!used[j]&&dis[j] > max(dis[Np],map[Np][j])){
				dis[j] = max(dis[Np],map[Np][j]);
//				pre[j] = Np;
			}
			
	}	
}

double calc(int i, int j) {
    return (sqrt(pow((double)node[i].x-node[j].x, 2)+pow((double)node[i].y-node[j].y, 2)));
}

int main()
{
    int t=1;
    while(~scanf("%d",&n)&&n)
    {
        for(int i=1; i<=n; i++)
            scanf("%d %d",&node[i].x,&node[i].y);
        for(int i=1; i<=n; i++)
            for(int j=i; j<=n; j++)
                map[i][j]=map[j][i]=calc(i, j);
        dijkstra();
        printf("Scenario #%d\nFrog Distance = %.3f\n\n",t++,dis[2]);

    }
}