http://acm.hdu.edu.cn/webcontest/contest_showproblem.php?cid=963pid=1019ojid=1

本文主要是介绍http://acm.hdu.edu.cn/webcontest/contest_showproblem.php?cid=963pid=1019ojid=1，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这一题是dijstra的变种，，，用的是dijstra的思想和方法，让求的是从一点到另一点的最大的最小值，，，，一开始木有认真读题，，，贡献了5次wa，，，

#include <iostream>
#include <cmath>
#include<cstdio>
using namespace std;
#define MAX 201
#define INF 10000.0f
float matrix[MAX][MAX];
int s[MAX];
float dis[MAX];
typedef struct point
{int x;int y;
}point;
void Dijkstra(int &n)
{         int now=1;for(int i = 1; i <= n; ++i){dis[i] = matrix[now][i];s[i] = 0;}s[now] = 1;for(int i = 1; i <= n-1; ++i){float minDis = INF;for(int j = 1; j <= n; ++j)if(!s[j] && dis[j] < minDis)minDis = dis[now=j];s[now] = 1;for(int j = 1; j <= n; ++j)if(!s[j] && matrix[now][j]!= INF)dis[j] = min(dis[j],max(dis[now],matrix[now][j]));}
}
int main()
{int n;point p[MAX];int count = 0;while(~scanf("%d",&n)&& n){for(int i = 1; i <= n; ++i)~scanf("%d%d", &p[i].x, &p[i].y);for(int i = 1; i <= n; ++i)for(int j = 1; j <= n; ++j)if(i!=j)  matrix[i][j] = INF;else    matrix[i][j] = 0;for(int i = 1; i < n; ++i)for(int j = i+1; j <=n; ++j)matrix[j][i] = matrix[i][j] = sqrt(((float)(p[i].x-p[j].x)*(p[i].x-p[j].x))+ (p[i].y-p[j].y)*(p[i].y-p[j].y));Dijkstra(n);printf("Scenario #%d\nFrog Distance = %.3f\n\n", ++count, dis[2]);}return 0;
}

这篇关于http://acm.hdu.edu.cn/webcontest/contest_showproblem.php?cid=963pid=1019ojid=1的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---