2009-3-12-pku1556.txt

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

#include<stdio.h>
#include<string.h>
#include<math.h>
const int MAX=2005;
const double INF=1e20;
//定义边
typedef struct Edge
{
	int st;
	int ed;
	double distance;
}Edge;
Edge edge[MAX];
//定义点
typedef struct Point
{
	double x;
	double y;
	int v;
}Point;
Point p[25][21];
Point pst,ped;
//定义线段
typedef struct LINESEG
{
	Point st;
	Point ed;
}LINESEG;
//求两点之间的距离
double dist(Point a,Point b)
{
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
//求两个向量的叉积
double multiply(Point a,Point b,Point c)
{
	return (a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x);
}
//返回最大值
double max(double x,double y)
{
	return x>y? x:y;
}
//返回最小值
double min(double x,double y)
{
	return x>y? y:x;
}
//判断连个线段是否相交
bool intersect(LINESEG u,LINESEG v)
{
	return max(u.st.x,u.ed.x)>=min(v.st.x,v.ed.x)
		&&max(v.st.x,v.ed.x)>=min(u.st.x,u.ed.x)
		&&max(u.st.y,u.ed.y)>=min(v.st.y,v.ed.y)
		&&max(v.st.y,v.ed.y)>=min(u.st.y,u.ed.y)
		&&multiply(v.st,u.ed,u.st)*multiply(u.ed,v.ed,u.st)>=0
		&&multiply(u.st,v.ed,v.st)*multiply(v.ed,u.ed,v.st)>=0;
}
//判断源点到到(i=2...n)墙之间是否能构成图的边
bool Judge(int n,Point q)
{
	int i;
	LINESEG L1,L2,L3;
	L1.st=pst,L1.ed=q;
	for(i=1;i<=n;i++)
	{
		L2.st=p[i][1],L2.ed=p[i][2];
		L3.st=p[i][3],L3.ed=p[i][4];
		if(!intersect(L1,L2)&&!intersect(L1,L3))
			return false;
	}
	return true;
}
//判断终点到(i=1...n-1)墙之间是否能构成图的边
bool Judge1(int st,int n,Point q)
{
	int i;
	LINESEG L1,L2,L3;
	L1.st=ped,L1.ed=q;
	for(i=st;i<=n;i++)
	{
		L2.st=p[i][1],L2.ed=p[i][2];
		L3.st=p[i][3],L3.ed=p[i][4];
		if(!intersect(L1,L2)&&!intersect(L1,L3))
			return false;
	}
	return true;
}
double d[MAX];
//初始化d[u]：用来描述从源点S到u的最短路径上权值的三界！
void Init(int V,int S)
{
	int i;
	for(i=1;i<=V;i++)
		d[i]=INF;//开始的时候设置为无穷大!
	d[S]=0;//源点设置为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].ed]=d[edge[j].st]+edge[j].distance,relaxed=false;
		if(relaxed)//说明当前这一轮没有进行松弛，那么以后将也不会进行松弛，那么就提前结束！
			break;
	}
	return relaxed;
}
int main()
{
	int i,j,k,E,V,n;
	double x,y;
	while(scanf("%d",&n)&&n!=-1)
	{
		V=1,E=0,pst.x=0,pst.y=5,pst.v=1;
		ped.x=10,ped.y=5;
		for(i=1;i<=n;i++)
		{
			scanf("%lf",&x);
			for(j=1;j<=4;j++)
			{
				scanf("%lf",&y);
				p[i][j].x=x,p[i][j].y=y,p[i][j].v=++V;
			}
		}
		ped.v=++V;
		//源点到第一个墙构成的边
		for(i=1;i<=4;i++)
			edge[++E].st=pst.v,edge[E].ed=p[1][i].v,edge[E].distance=dist(pst,p[1][i]);
		//终点到第N个墙够成的边
		for(i=1;i<=4;i++)
			edge[++E].st=p[n][i].v,edge[E].ed=ped.v,edge[E].distance=dist(ped,p[n][i]);
		//任何两个墙之间构成的图的边
		for(i=1;i<=n-1;i++)
		{
			for(j=1;j<=4;j++)
				for(k=1;k<=4;k++)
					edge[++E].st=p[i][j].v,edge[E].ed=p[i+1][k].v,edge[E].distance=dist(p[i][j],p[i+1][k]);
		}
		//源点到(i=2...n)墙之间构成图的边
		for(i=2;i<=n;i++)
		{
			for(j=1;j<=4;j++)
				if(Judge(i-1,p[i][j]))
					edge[++E].st=pst.v,edge[E].ed=p[i][j].v,edge[E].distance=dist(pst,p[i][j]);
		}
		//终点到(i=1...n-1)墙之间构成图的边
		for(i=1;i<=n-1;i++)
		{
			for(j=1;j<=4;j++)
				if(Judge1(i+1,n,p[i][j]))
					edge[++E].st=p[i][j].v,edge[E].ed=ped.v,edge[E].distance=dist(ped,p[i][j]);
		}
		//源点到终点构成的图的边
		if(Judge(n,ped))
			edge[++E].st=pst.v,edge[E].ed=ped.v,edge[E].distance=dist(pst,ped);
		//求最短路径算法！
		Bellman_Ford(V,E,1);
		printf("%.2lf\n",d[V]);
	}
	return 0;
}
/*
1
5 4 6 7 8
2
4 2 7 8 9
7 3 4.5 6 7
-1



10.00
10.06
*/