本文主要是介绍UVa10803 - Thunder Mountain，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：坐标系内有n个点，距离小于等于10的任意两点之间有边。求任意两点之间最短路中最大的那个。
思路：Floyd算法，水题。注意两点间距离大于10是没有边的。
#include <iostream>
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <cstdlib>
#include <string>
#include <memory.h>
#include <vector>
#include <queue>
#include <stack>
#include <ctype.h>
#define INF 1000000000
using namespace std;double townx[110];
double towny[110];
double ans[110][110];double dist(double x1,double y1,double x2,double y2){return sqrt( (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2) );
}int main(){int N;cin>>N;for(int t=1;t<=N;t++){int n;cin>>n;for(int i=1;i<=n;i++){scanf("%lf%lf",&townx[i],&towny[i]);}//init for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){ans[i][j]=INF;}}for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){double dis1=dist(townx[i],towny[i],townx[k],towny[k]);if(dis1>10)dis1=ans[i][k];double dis2=dist(townx[j],towny[j],townx[k],towny[k]);if(dis2>10)dis2=ans[j][k];if( (dis1+dis2)<ans[i][j]&&(dis1<10.001||ans[i][k]<INF-1)&&(dis2<10.001||ans[j][k]<INF-1)){ans[i][j]=(dis1+dis2);}}}}double farest=0;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){farest=max(farest,ans[i][j]);}}printf("Case #%d:\n",t);if(farest>INF-1){printf("Send Kurdy\n\n");}else{printf("%.4lf\n\n",farest);}}return 0;
}
这篇关于UVa10803 - Thunder Mountain的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
