题目大意：比较明显的题目，在一个房间中有几堵墙，直着走，问你从（0，5）到（10，5）的最短路是多少
求最短路问题，唯一变化的就是边的获取，需要我们获取边，这就需要判断我们想要走的这条边会不会经过墙
所以创建点集，线段集合
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string.h>
#include <iomanip>
#define eps 1e-10
#define inf 0x3f3f3f3f
#define equal(a,b) fabs((a) - (b)) < eps
using namespace std;
const int maxn = 200;
int pnum,lnum;
struct Point
{
double x,y;
Point(double x = 0.0,double y = 0.0):x(x),y(y){}
Point operator - (Point p){return Point(x-p.x,y-p.y);}
}ps[maxn];
struct segment
{
Point p1,p2;
segment(Point p1 = Point(0.0,0.0),Point p2 = Point(0.0,0.0)):p1(p1),p2(p2){}
}ls[maxn];
//存储线段和点~~
事先也要准备好最短路的东西
double mp[maxn][maxn]; double dis[maxn]; int vis[maxn];
int main()
{
int n;
double x,y1,y2,y3,y4;
while(~scanf("%d",&n),n != -1)
{
init();
ps[pnum++] = Point(0,5);
for(int i = 0;i < n;i++)
{
scanf("%lf%lf%lf%lf%lf",&x,&y1,&y2,&y3,&y4);
ps[pnum++] = Point(x,y1);
ps[pnum++] = Point(x,y2);
ps[pnum++] = Point(x,y3);
ps[pnum++] = Point(x,y4);
ls[lnum++] = segment(Point(x,0),Point(x,y1));
ls[lnum++] = segment(Point(x,y2),Point(x,y3));
ls[lnum++] = segment(Point(x,y4),Point(x,10));
}
ps[pnum] = Point(10,5);
for(int i = 0;i <= pnum;i++)
{
for(int j = 0;j <= pnum;j++)
{
if(i == j)mp[i][j] = 0.0;
else if(checkline(i,j))
{
mp[i][j] = getdis(i,j);
//printf("%d %d
",i,j);
//cout<<mp[i][j]<<endl;
//cout<<mp[i][j]<<endl;
}
else mp[i][j] = inf * 1.0;
}
}
dijkscar(0,pnum);
cout << fixed << setprecision(2) << dis[pnum] << endl;
}
return 0;
}
main函数中是输入点和线段至对应的集合中，然后去找合适的边填充mp二维数组，这是侯用到了线段相交的判断
bool intersect(int i,int j,int k)
{
if(cross(ps[i],ps[j],ls[k].p1) * cross(ps[i],ps[j],ls[k].p2) < -eps &&
cross(ls[k].p1,ls[k].p2,ps[i]) * cross(ls[k].p1,ls[k].p2,ps[j]) < -eps)return true;
return false;
}
bool checkline(int i,int j)
{
for(int k = 0;k < lnum;k++)
{
//printf("k = %d && i = %d && j = %d Point[i] = (%d,%d),Point[j] = (%d,%d),Segment = %d %d %d %d
",k,i,
// j,(int)ps[i].x,(int)ps[i].y,(int)ps[j].x,(int)ps[j].y,(int)ls[k].p1.x,(int)ls[k].p1.y,(int)ls[k].p2.x,(int)ls[k].p2.y);
if(intersect(i,j,k))
return false;
}
return true;
}
double cross(Point p1,Point p2,Point p3)
{
Point a = p2 - p1;
Point b = p3 - p1;
return a.x * b.y - a.y * b.x;
}
线段是否相交，利用外积的方向判断，如果双方都符合一条线段的两个端点在另一条线段的两个端点时，就会相交
然后时常规的dijkscar算法
void dijkscar(int s,int n)
{
for(int i = 1;i <= n;i++)dis[i] = mp[s][i];
dis[s] = 0;
vis[s] = 1;
for(int i = 0;i <= n;i++)//优化次数
{
double minlen = inf * 1.0;
int net = 0;
for(int j = 1;j <= n;j++)
{
if(!vis[j] && dis[j] < minlen)
{
minlen = dis[j];
net = j;
}
//if(net == 0)break;
//if(minlen == inf * 1.0)break;
vis[net] = 1;
for(int j = 1;j <= n;j++)
{
if(dis[j] > dis[net] + mp[net][j])
{
dis[j] = dis[net] + mp[net][j];
}
}
}
}
}
我犯的几个错误
dijkscar中if(net == 0)break;这句话导致我最短路判断失误，我目前也不知道什么原因
符合条件的边输入进mp数组，我以为只要输入单向向右的就行了所以一开始的for循环时i = 0 -> n - 1 + j = i + 1 - > n，结果发现，emm还是有特殊情况的，比如径直往上走的情况~~