题目链接：http://poj.org/problem?id=2253
题意：求青蛙一到青蛙二之间经过所有跳跃点的最长路径中的最小值
dijkstra ac code：
#pragma GCC optimize(3,"Ofast","inline") #pragma GCC optimize(2) #include<iostream> #include<cmath> #include<cstdlib> #include<cstdio> #include<cstring> #include<algorithm> #define NIL -1 #define INF 0x3f3f3f3f using namespace std; const int maxn=210; int n,vis[maxn]; double dis[maxn],graph[maxn][maxn]; struct node{ double x,y; }; node nd[maxn]; double distance(double x1,double x2,double y1,double y2) { return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)); } void dijkstra() { for(int i=1;i<=n;i++){vis[i]=0;dis[i]=INF;} dis[1]=0; while(1){ int minv=INF,u=-1; for(int i=1;i<=n;i++){if(!vis[i]&&dis[i]<minv){minv=dis[i];u=i;}} if(u==-1)break; vis[u]=1; for(int v=1;v<=n;v++){ if(vis[v])continue; dis[v]=min(dis[v],max(dis[u],graph[u][v])); } } } int main() { int kase=0; while(cin>>n){ if(n==0)break; memset(graph,0,sizeof(graph)); double x,y; for(int i=1;i<=n;i++){ cin>>x>>y; nd[i].x=x;nd[i].y=y; } for(int i=1;i<=n;i++){ for(int j=1;j<=i;j++){ graph[i][j]=graph[j][i]=distance(nd[i].x,nd[j].x,nd[i].y,nd[j].y);//无向图记得把ij和ji位置的权值赋成同一个 } } dijkstra(); printf("Scenario #%d\nFrog Distance = %.3lf\n\n",++kase,dis[2]);//输出格式也要小心，我之前一直在#后面加了个冒号，一直wa又没报pe，心好塞，后来才发现是输出格式的问题 } return 0; }Floyd：
