2009-2-20pku2253.txt

数据结构中的单元最短路径算法的题目和源代码！其中所有的题目都能在PKU上找的到！

/*
题意 ：两个forger 一个froger 要蹦到另外一个froger处 他们的最短距离是这样定义的 ：
 The frog distance (humans also call it minimax distance) between two stones therefore is defined as the minimum necessary
 jump range over all possible paths between the two stones.
 即为 ：两个石头之间的frog distance就是在这两个石头之间的所有路径中最大跳(necessary jump range)最小的。 
 (以上引自aowarmen's blog)

想法 ：我们通常的dj方法的最短路径是进行边的松弛，判断条件为 d[i] > d[w] + map[w][i]  即对边的松弛，根据三角不等式，
       更新后为 d[i]=d[w]+map[w][i];而这个“最短路径”通过的路径里面的最大值，只是判断条件和更新变一下。  
       即 d[j]>(d[w]>map[w][i]?d[w]:map[w][i]) 更新为选择点的最短距离d[w]和(u,v)的距离里面最大的那个进行更新.
       即 d[i]=d[w]>map[w][i]?d[w]:map[w][i]; 

ps : 看discuss里面有用最小生成树做的，而且aowarmen是用参数搜索做出来的，同样0ms，想不通 + ym中。。。请各位知道的。
     或者有更好的方法的，  能提示一下。

代码如下 ：

*/
#include<stdio.h>
#include<math.h>
const int MAXV=405;
const int MAXE=40915;
const double INF=1e100;
typedef struct Edge
{
	int st;
	int ed;
	double distance;
}Edge;
Edge edge[MAXE];
typedef struct Point
{
	double x;
	double y;
}Point;
Point p[MAXV];
double d[MAXV];
int num;
//初始化d[u]：用来描述从源点S到u的最短路径上权值的上界！
void Init(int V,int S)
{
	int i;
	for(i=1;i<=V;i++)
		d[i]=INF;//开始的时候设置为无穷大!
	d[S]=0;//源点设置为
}
//Bellman_Ford算法的实现!
bool Bellman_Ford(int V,int E,int S)
{
	int i,j;
	bool relaxed;//优化
	Init(V,S);
	for(i=1;i<=V-1;i++)
	{
		relaxed=true;
		for(j=1;j<=E;j++)
			if(d[edge[j].ed]>(d[edge[j].st]>edge[j].distance?d[edge[j].st]:edge[j].distance))
				d[edge[j].ed]=d[edge[j].st]>edge[j].distance?d[edge[j].st]:edge[j].distance,relaxed=false;
		if(relaxed)//说明当前这一轮没有进行松弛，那么以后将也不会进行松弛，那么就提前结束！
			break;
	}
	return relaxed;
}
double Dis(Point a,Point b)
{
	double dis;
	dis=(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
	return sqrt(dis);
}
int main()
{
	int V,E,i,j;
	int count=0;
	while(scanf("%d",&V),V)
	{
		E=0;
		for(i=1;i<=V;i++)
			scanf("%lf%lf",&p[i].x,&p[i].y);
		for(i=1;i<=V-1;i++)
			for(j=i+1;j<=V;j++)
			{
				edge[++E].st=i;
				edge[E].ed=j;
				edge[E].distance=Dis(p[i],p[j]);
				edge[++E].st=j;
				edge[E].ed=i;
				edge[E].distance=Dis(p[i],p[j]);
			}
		bool flag=Bellman_Ford(V,E,1);
		printf("Scenario #%d\n",++count);
		printf("Frog Distance = %.3lf\n\n",d[2]);
	}
	return 0;
}
/*
2
0 0
3 4

3
17 4
19 4
18 5

0

Scenario #1
Frog Distance = 5.000

Scenario #2
Frog Distance = 1.414





这道题目开头理解不是太好后来连续读了好几次猜明白了，讲一下我的理解吧！
题目要求找出最短路径，然后再找出路径中边的最大权值，就是从最短路径中找边的最大值，
如果几条路径长度相同就选择跳跃距离最短的路径。
eg: 5 5 6 6       //总长度为22
    2 2 2 2 2 2 2 2 2 2 2   //总长度也为22
我们就选择下面那条作为最短路径然后最大的跳跃距离就是2了

*/