由于前几天看的SPFA，然后我一看题，想都没想就拿SPFA来写了，果断超时，不对。应该可以的，还是我没学到家。不对。
然后我知道这样不行，不能一求最短路啥的就想都不想就那SPFA来写，就今天上午系统的看了下dijkstra,kruskal,prim,spfa,flyod,把这几个都看了，系统的了解了一下，然后我中午用的dijkstra写的，果断又wa！！！！！一翻disscuss，有人说%f,%lf要注意，我把%lf改成了%f，然后果断过了。微艰难。
这题目松弛的时候就是 dist[u]<=dist[k]&&gird[u][k]<dist[k]. //dist表示从1位置到该位置所需跳跃的最大值。gird[][]表示两位置之间的距离。然后dist[k]=max(dist[k],gird[u][k]）
#include <iostream> #include <stdio.h> #include <queue> #include <algorithm> #include <string.h> #include <cmath> #define maxn 200+10 #define INF 0xfffffff using namespace std; bool inq[maxn]; double dist[maxn]; int S[maxn]; double gird[maxn][maxn]; int path[maxn]; int n; queue<int>Q; double ssqrt(int a,int b) { double t; t= sqrt( a*a+b*b ); return t; } double dijkstra(int begin) { int i,j,k; for(i=1;i<=n;++i) { dist[i]=gird[begin][i]; S[i]=0; } S[begin]=1; dist[begin]=0; for(i=1;i<=n;++i) { double min=INF; int u=begin; for(j=1;j<=n;++j) { if(!S[j]&&dist[j]<min) { u=j; min=dist[j]; } } S[u]=1; for(k=1;k<=n;++k) { if(!S[k] && ( dist[u]<dist[k]&&gird[u][k]<dist[k] ) ) { dist[k]=( dist[u]>gird[u][k]?dist[u]:gird[u][k] ); } } } return dist[2]; } int main() { int i,j; int x[maxn],y[maxn]; double res; int cnt=0; while(~scanf("%d",&n)&&n) { for(i=1;i<=n;++i) { scanf("%d%d",&x[i],&y[i]); } for(i=1;i<=n;++i) //init the graph { for(j=1;j<=n;++j) { gird[i][j]=gird[j][i]=ssqrt(x[i]-x[j],y[i]-y[j]); } } res=dijkstra(1); printf("Scenario #%d\n",++cnt); printf("Frog Distance = %.3f\n",res); printf("\n"); } return 0; }