题目链接：http://poj.org/problem?id=2253
#include#include #include #include #include #define MAX 205#define INF 0x3f3f3f3fusing namespace std;/**************************************************************************************************************** 题意：题目的意思是，Freddy青蛙要找Fiona青蛙，Freddy青蛙在第1块石头那里，而Fiona青蛙在第2块石头那里。 现在Freddy青蛙要以周围的石头为中介跳向Fiona青蛙。考虑到有很多种跳法， Freddy青蛙想要选择一条路线，使它在这条路线上可以跳的最大距离，小于其它任何路线上可以跳的最大距离。 思路： 1，这题就是按着dijkstra写，写着写着觉得像是prim了。 2，其中dist[n]表示从1出发到达该点的某条路中的最大边，且比其它可能的路中的都小。 3，从dist[i]到dist[j], 就是要用 max(dist[id], Map[id][j]) 去更新 dist[j] 。 4，不是很理解为什么这么做。目的是求第一个点到第二点的最小生成树的最短距离！！！ 待续。。。。。。 注意： 输出时要用 %.3f 不能用 %.3lf.****************************************************************************************************************/pair < int, int > Coor[MAX];double Map[MAX][MAX];double dist[MAX];int visit[MAX];double Distance( const pair< int, int > &A, const pair< int, int > &B ){ return sqrt(double((A.first-B.first)*(A.first-B.first)+(A.second-B.second)*(A.second-B.second)));}void dijkstra(int n){ memset(dist,INF,sizeof(dist)); memset(visit,0,sizeof(visit)); for(int i = 1;i <= n;i ++) dist[i]=Map[1][i]; dist[1]=0; visit[1]=1; for(int i = 1;i < n;i ++){ int id=1; double ans=INF; for(int j = 1;j <= n;j ++) if(!visit[j] && dist[j] < ans) ans=dist[id=j]; if(id == 1) return ; visit[id]=1; for(int j = 1;j <= n;j ++) if(!visit[j] && dist[j] > max(dist[id],Map[id][j])) dist[j]=max(dist[id],Map[id][j]); //更新和普通dijkstra不同 }}int main(){ int n; int cnt=1; while(cin>>n,n) { memset(Map,INF,sizeof(Map)); for(int i = 1;i <= n;i ++){ cin>>Coor[i].first>>Coor[i].second; for(int j = 1;j < i;j ++) Map[i][j]=Map[j][i]=Distance(Coor[i],Coor[j]); Map[i][i]=0; } dijkstra(n); printf("Scenario #%d\nFrog Distance = %.3f\n\n",cnt++,dist[2]); } return 0;}