- 时间限制: 1000 ms 内存限制: 65535 K
- 问题描述
-
小青蛙和他的妈妈走散了,怎么办呢?小青蛙好着急阿,他就在荷叶上跳来跳去找他的妈妈呀,妈妈,妈妈,你在哪儿?妈妈说,我在这儿呀。你快过来。
小青蛙太小了,他的弹跳能力实在太低了,我们必须找到一条路,让他能够最轻松跳过去。妈妈在位置1 ,而小青蛙在位置2.
青蛙只能在荷叶上跳来跳去,我们需要知道小青蛙至少需要多少跳远能力才能够到妈妈那儿去呢? - 输入
-
第一行有一个整数N,以0结尾,表示荷叶数. 2 <= N <= 200
然后下面有N行,每行是一个坐标(Xi,Yi),表示荷叶的位置.-100 <= Xi,Yi <= 100 - 输出
-
对于每组输出,如样例.每组输出后空一行.
- 样例输入
-
2 0 0 3 4 3 17 4 19 4 18 5 0
- 样例输出
-
Case #1 Distance = 5.000 Case #2 Distance = 1.414
- 提示
-
无
- 来源
-
zyvas
一开始用floyd算法变形,结果超时,然后用了传统的dijkstra算法变形。
#include<stdio.h> #include<string.h> #include<math.h> #include<algorithm> #include<iostream> #include<map> #include<vector> #include<set> #include<iterator> #include<queue> #define inf 0x3f3f3f3f using namespace std; const int maxn=210; double mat[maxn][maxn]; struct point { int x,y; }node[maxn]; double dijkstra(int v,int n) { bool used[maxn]; double dist[maxn]; for(int i=1;i<=n;i++) { used[i]=0; dist[i]=mat[v][i]; } dist[v]=0; used[v]=1; for(int i=2;i<=n;i++) { double mins=inf; int u; for(int j=1;j<=n;j++) { if(!used[j] && dist[j]<mins) { mins=dist[j]; u=j; } } used[u]=1; for(int j=1;j<=n;j++) { if(!used[j] && dist[j]<inf) { if(dist[j]>max(dist[u],mat[u][j])) dist[j]=max(dist[u],mat[u][j]); } } } return dist[2]; } double dis(point a,point b) { return sqrt((double)(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } int main() { int n,icase=1; while(~scanf("%d",&n) && n) { memset(mat,inf,sizeof(mat)); 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=1;j<i;j++) mat[i][j]=mat[j][i]=dis(node[i],node[j]); printf("Case #%d\n",icase++); printf("Distance = %.3f\n\n",dijkstra(1,n)); } return 0; }