本文主要是介绍POJ 2253Frogger(dijk最短路变形），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目地址：http://poj.org/problem?id=2253
这题刚开始理解错题目意思了，以为就只是简单的求个最短路，后来找题解翻译才发现完全理解错题目意思了。
这题实际是求的最短路的最长边。看翻译的过程中不小心看到了题解。。。然后不小心发现只改变了一句话。。其实就是最短路的变形，花时间理解了下那句话的含义，就是把原先记录的到某结点的最短距离改成了最长边更短的路径的最长边（略绕口。。）。
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <queue>
#include <map>
#include <algorithm>using namespace std;
double swap1(double x, double y)
{if(x>y)return x;return y;
}
struct node
{int x, y;
}q[300];
double mp[210][210], d[210], maxint=99999999;
int n, vis[210];
void dijk()
{int i, j, pos;double min1;memset(vis,0,sizeof(vis));for(i=0;i<n;i++)d[i]=mp[0][i];d[0]=0;vis[0]=1;for(i=0;i<n;i++){min1=maxint;for(j=0;j<n;j++){if(!vis[j]&&min1>d[j]){min1=d[j];pos=j;}}vis[pos]=1;for(j=0;j<n;j++){if(!vis[j]&&d[j]>swap1(d[pos],mp[pos][j]))//(这句话是重点，需要好好体会）{d[j]=swap1(d[pos],mp[pos][j]);}}}printf("%.3lf\n\n",d[1]);
}
int main()
{int i, j, x, y, num=0;double s;while(scanf("%d",&n)!=EOF&&n){memset(mp,maxint,sizeof(mp));num++;for(i=0;i<n;i++){scanf("%d%d",&q[i].x,&q[i].y);for(j=0;j<i;j++){s=sqrt((q[i].x-q[j].x)*(q[i].x-q[j].x)*1.0+(q[i].y-q[j].y)*(q[i].y-q[j].y)*1.0);mp[i][j]=mp[j][i]=s;}}printf("Scenario #%d\nFrog Distance = ",num);dijk();}return 0;
}
这篇关于POJ 2253Frogger(dijk最短路变形）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
