这个题一开始不知道咋做，但是大致有点意思。后来还是借鉴了题解发现可以用dijkstra，不太理解。但是在最后自己推的时候突然理解了。
dijkstra应该也算是动态规划。我们用dis[i]数组作为青蛙跳到第i个石头时途经的最大跳跃距离。借鉴dijkstra的思路，先找最小的dis[i].然后i作为中间点修改dis[j]，
1<=j<=n;并且U[i]==0;那么对于修改的时候对于点j如果dis[j]>max(dis[i],arcs[i][j]),那么肯定有修改的必要，新的dis[i]=max(dis[i],arcs[i][j])。至于为什么可以这样呢，其实是和dijkstra的证明类似的，但是这里有一个简单的思路。因为我们一开始对于每个点就有最初的dis[j]，当我们可以借助中间点逐渐优化的时候，那么dis[j]肯定是越来越优化的，直到结束。其实这样想有点像floyd。动态规划真的是神奇啊！
Ps：今天历经坎坷，终于组队了。虽然水平都不高，但是距离区域赛还有6个月！we can make it!
1 #include <iostream> 2 #include <cstring> 3 #include <string> 4 #include <map> 5 #include <set> 6 #include <algorithm> 7 #include <fstream> 8 #include <cstdio> 9 #include <cmath> 10 #include <stack> 11 #include <queue> 12 #define lson l,m,rt<<1 13 #define rson m+1,r,rt<<1|1 14 using namespace std; 15 const double Pi=3.14159265358979323846; 16 typedef long long ll; 17 const int MAXN=200+5; 18 const int dx[4]={0,0,1,-1}; 19 const int dy[4]={1,-1,0,0}; 20 const int INF = 0x3f3f3f3f; 21 const int NINF = 0xc0c0c0c0; 22 const ll mod=1e9+7; 23 struct graph 24 { 25 double weight; 26 double arcs[MAXN][MAXN]; 27 }G; 28 struct node{ 29 int a,b; 30 }p[MAXN]; 31 double dis[MAXN]; 32 //v是起点，n是一共的点的个数 33 //dis[i]记录的是从七点到i，所有路径中的最小单步值 34 void dijkstra(int v,int n) 35 { 36 int U[MAXN]; 37 for(int i=1;i<=n;i++) U[i]=0; 38 for(int i=1;i<=n;i++) dis[i]=INF; dis[v]=0; 39 40 for(int i=1;i<=n;i++) 41 { 42 double minn=INF;int k=-1; 43 /*for(int j=1;j<=n;j++) 44 { 45 cout <<dis[j]<<" "; 46 } 47 cout <<endl<<"**********"<<endl;*/ 48 for(int i=1;i<=n;i++) 49 { 50 if(minn>dis[i]&&U[i]==0) 51 { 52 minn=dis[i]; 53 k=i; 54 } 55 } 56 U[k]=1; 57 58 for(int i=1;i<=n;i++) 59 { 60 if(U[i]==0&&dis[i]>max(G.arcs[i][k],dis[k])) 61 { 62 dis[i]=max(G.arcs[i][k],dis[k]); 63 } 64 } 65 } 66 } 67 int main() 68 { 69 int n;int cnt=1; 70 while(scanf("%d",&n)&&n) 71 { 72 for(int i=1;i<=n;i++) 73 { 74 scanf("%d%d",&p[i].a,&p[i].b); 75 } 76 for(int i=1;i<n;i++) 77 { 78 for(int j=i+1;j<=n;j++) 79 { 80 G.arcs[i][j]=sqrt((p[i].a-p[j].a)*(p[i].a-p[j].a)+(p[i].b-p[j].b)*(p[i].b-p[j].b)); 81 G.arcs[j][i]=G.arcs[i][j]; 82 } 83 } 84 dijkstra(1,n); 85 printf("Scenario #%d\n",cnt++); 86 printf("Frog Distance = %.3f\n\n",dis[2]); 87 } 88 return 0; 89 }
原文：https://www.cnblogs.com/Msmw/p/10543224.html
