题意：求1到2所有路径中最小蛙跳 蛙跳：在一条路径中所有蛙跳中的最大蛙跳
思路：dijska算法思想
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63 |
#include<iostream>#include<cmath>using
namespace std;struct
Node{ double
x,y;}node[222];double
dist[222];int s[222];int
n;int
cas;double
e(Node a,Node b){ return
sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}double
max(double
x,double
y){ if(x>y) return
x; return
y;}void
Dijsc(){ int
i,j,v; memset(s,0,sizeof(s)); for(i=1;i<=n;i++) dist[i]=e(node[1],node[i]); s[1]=1; for(i=1;i<=n;i++) { v=-1; double
min=999999999; for(j=2;j<=n;j++) { if(dist[j]<min&&!s[j]) //每次选择最小蛙跳 向外扩展 所选择的这个蛙跳肯定是最小的 也就是最优的 v=j,min=dist[j]; } if(v==-1) break;s[v]=1; for(j=2;j<=n;j++)//通过最小的蛙跳向外扩展 { if((dist[j]>dist[v])&&(dist[j]>e(node[v],node[j]))) dist[j]=max(dist[v],e(node[v],node[j])); } }printf("Scenario #%d\n",cas);printf("Frog Distance = %.3f\n\n",dist[2]);}int
main(){ int
i; cas=0; while(scanf("%d",&n)!=EOF) { if(n==0) break; cas++; for(i=1;i<=n;i++) scanf("%lf%lf",&node[i].x,&node[i].y); Dijsc(); } return
0;} |
原文：http://www.cnblogs.com/zhangdashuai/p/3772657.html