Description
Input
Output
Sample Input
2 0 0 3 4 3 17 4 19 4 18 5 0
Sample Output
Scenario #1 Frog Distance = 5.000 Scenario #2 Frog Distance = 1.414
题目大意：给出n个点的坐标，源点是1，终点是2。问你一条从源点能到达终点的路径中的最长边且满足不大于其他可到达终点路径中的最小边长度。（即求最长边的最小值）。
解题思路：改变SPFA中的d数组的含义，在更新d数组的时候条件也变一下。d[i]表示从源点到i点的最长边最小值。那么更新条件就变为if( d[i] > max( d[u] ,distance(u,i) ) ) d[i] = max(d[u] , distance (u,i) )。表示当前在u点时，如果路径中的最长边长度，跟 distance( u ,i )的最大值还小于d[i]（i点的最大边长度），那么说明原来到达i点时的最长边还不够小，那么更新即可。
结果必须输出%.3f，而不是%.3lf。这里一直错。
#include<stdio.h>
#include<algorithm>
#include<queue>
#include<vector>
#include<math.h>
#include<string.h>
using namespace std;
const int maxn = 1e4;
const int INF = 0x3f3f3f3f;
struct HeapNode{
double d;
int u;
bool operator < (const HeapNode &rhs)const {
return d > rhs.d;
}
};
struct Edge{
int from,to;
double dist;
};
struct node{
double x,y;
}cor[maxn];
priority_queue<HeapNode>PQ;
vector<Edge>edge;
vector<int>G[maxn];
double d[maxn];
int vis[maxn];
int n,m;
double distan(node a, node b){
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
void AddEdge(int u,int v,double dis){
edge.push_back((Edge){u,v,dis});
m = edge.size();
G[u].push_back(m-1);
}
void SPFA(int s){
for(int i = 0; i<= n;i++){
d[i] = INF;
}
memset(vis,0,sizeof(vis));
d[s] = 0.00;
PQ.push( (HeapNode){d[s],s} );
while(!PQ.empty()){
HeapNode x = PQ.top();
PQ.pop();
int u = x.u;
if(u == 1){
break;
}
if(vis[u]) continue;
vis[u] = 1;
for(int i = 0; i < G[u].size(); i++){
Edge & e = edge[G[u][i]];
if( (!vis[e.to]) && d[e.to] > max( d[e.from], e.dist) ){
d[e.to] = max(d[e.from] , e.dist);
PQ.push( (HeapNode){ d[e.to] , e.to } );
}
}
}
}
void init(int n){
for(int i = 0; i <= n;i++){
G[i].clear();
}
edge.clear();
while(!PQ.empty())
PQ.pop();
}
int main(){
int cnt = 0;
while(scanf("%d",&n)!=EOF && n){
init(n);
for(int i = 0; i < n; i++){
scanf("%lf%lf",&cor[i].x,&cor[i].y);
for(int j = 0; j < i; j++){
AddEdge( i, j, distan(cor[i],cor[j]));
AddEdge( j, i, distan(cor[j],cor[i]));
}
}
SPFA(0);
printf("Scenario #%d\n",++cnt);
printf("Frog Distance = %.3f\n",d[1]);
puts("");
}
return 0;
}
/*
这里给出4个点6条边，不是坐标表示
4 6
1 4 3
1 2 4
1 3 5
2 4 2
3 4 6
2 3 8
可以看出为什么需要改成那样的更新条件
*/
POJ 2253 ——Frogger——————【最短路变型】
原文：http://www.cnblogs.com/chengsheng/p/4894831.html