原题链接

题解

1.最短路径一定可以表示成经过若干端点的线段，所以我们把端点单独提出来，这样就变成了计算几何形式的最短路
2.如果两个端点能相连，代表他们之间没有墙阻挡

code

#include<bits/stdc++.h>
using namespace std;
int n;

struct
{
    double x,a1,b1,a2,b2;
}wall[30];

int cnt=0;
struct
{
    double x,y;
}node[100];

vector<int> G[100];

void add(double x,double y)
{
    node[++cnt].x=x;
    node[cnt].y=y;
}

int disturb(int a,int b)//判断两点之间有没有被阻挡
{
    double x1=node[a].x,x2=node[b].x,y1=node[a].y,y2=node[b].y;
    double k=(y2-y1)/(x2-x1);

    for(int i=1;i<=n;i++)
    {
        if(wall[i].x<=x1||wall[i].x>=x2) continue;

        double y3=k*(wall[i].x-x1)+y1;
        //printf("node:%d,%d   wall:%d  y:%.2lf\n",a,b,i,y3);
        if(wall[i].a1<=y3&&y3<=wall[i].b1||wall[i].a2<=y3&&y3<=wall[i].b2) continue;
        else return 1;
    }
    return 0;
}
double cal(int a,int b)
{
    return sqrt((node[a].x-node[b].x)*(node[a].x-node[b].x)+(node[a].y-node[b].y)*(node[a].y-node[b].y));
}

struct fresh
{
    int id;
    double val;
    bool operator<(const fresh &b) const {return b.val<val;}
};

int main()
{
    cin>>n;
    add(0,5);
    for(int i=1;i<=n;i++)
    {
        cin>>wall[i].x>>wall[i].a1>>wall[i].b1>>wall[i].a2>>wall[i].b2;
        double x=wall[i].x;
        add(x,wall[i].a1);//单独提出来
        add(x,wall[i].b1);
        add(x,wall[i].a2);
        add(x,wall[i].b2);
    }
    add(10,5);
    for(int i=1;i<cnt;i++)
    {
        for(int j=i+1;j<=cnt;j++)
        {
            if(node[i].x==node[j].x) continue;
            if(!disturb(i,j)) G[i].push_back(j);//建边
        }
    }

    /*for(int i=1;i<=cnt;i++)
    {
        printf("%d:  ",i);
        for(auto it:G[i]) cout<<it<<" ";
        puts("");
    }*/

    double dis[100];

    for(int i=1;i<=cnt;i++) dis[i]=2e9;

    priority_queue<fresh> q;
    q.push({1,0});//最短路
    while(q.size())
    {
        int now=q.top().id;
        double val=q.top().val;
        q.pop();
        if(dis[now]<=val) continue;
        dis[now]=val;
        for(auto next:G[now])
        {
            double dist=cal(now,next);
            if(dist+dis[now]<dis[next]) q.push({next,dis[now]+dist});
        }
    }
    //for(int i=1;i<=cnt;i++) printf("%d : %.2lf\n",i,dis[i]);
    printf("%.2lf",dis[cnt]);
    return 0;
}