题解 P1354 【房间最短路问题】

· · 题解

既然这是一道图论题，那我们就要考虑建图。
这里把图搬出来：

虽然在这个房间里可以用很多种走法，但实际上图的节点只有墙壁的端点和始末点就行了。
就比如 (4,2),(4,7),(4,9),(7,4.5) 等点，然后把这些点相连建图即可。

光是这样还不行的，我们注意到有一些节点之间连成的线段是被墙隔断的。那我就需要写一个函数，来判断一条线段是否与一条平行于 y 轴的线段（也就是墙壁）有交点。

设线段的两端点分别为 (x_1,y_1) 和 (x_2,y_2)，可以得出其所在直线的方程（由于 x_2\neq x_1 所以可以这样写）：

y = \frac{y_2-y_1}{x_2-x_1}(x-x_1)+y_1

那么只需要令 x 为墙壁所在的横坐标，判断 y 值是否在墙壁的两端之间。

建图的问题也解决了，由于数据范围很小，随便选择一种最短路算法都能通过。

参考代码：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#define inf 0x3f3f3f3f
#define ll long long
#define N 1003
#define M 24
using namespace std;

struct edge{//求最短路用,图的边,w即距离
    int v;
    double w;
    edge(int v=0,double w=0):v(v),w(w){}
};

struct node{//求最短路用,图的节点,d为到源点距离
    int id;
    double d;
    node(int id=0,double d=0):id(id),d(d){}
    bool operator < (const node& n1) const{
        return d > n1.d;
    }
};

struct point{//平面直角坐标系中的一个点
    double x,y;
    point(double x=0,double y=0):x(x),y(y){}
};

struct wall{//记录一堵墙,y1,y2分别为墙的上、下纵坐标
    double x,y1,y2;
    wall(double x=0,double y1=0,double y2=0):x(x),y1(y1),y2(y2){}
};

double d[N];
point pt[M*4];
wall wl[M*3];
double x,a1,b1,a2,b2;
vector<edge> adj[N]; //vector存图
int n,m = 0,s,wallCount;
//n为节点数,m为边数,s为源节点(也就是1号节点,入口)

inline double dis(double x1,double y1,double x2,double y2){
    //计算平面直角坐标系中两点距离
    return sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
}

inline bool intersect(point pt1,point pt2,wall wal){
    //判断路径是否与墙相交
    double wlx = wal.x,y1 = wal.y1,y2 = wal.y2;
    if(pt1.x==pt2.x) return true;
    double k = (pt1.y-pt2.y)/(pt1.x-pt2.x);
    double b = pt1.y-k*pt1.x;
    double wyy = k*wlx+b; //wyy可爱。
    return (wyy<y1 && wyy>y2 && pt1.x<wlx && pt2.x>wlx);
    //交点在墙上,也在路径上
}

void dijkstra(){
    //dijkstra求最短路,SPFA已死
    s = 1;
    for(int i=1;i<=n;++i) d[i] = inf;
    d[s] = 0;
    priority_queue<node> q;
    q.push(node(s,0));
    while(!q.empty()){
        int u,v,l;
        u = q.top().id;
        double du = q.top().d;
        q.pop();
        if(du>d[u]) continue;
        l = adj[u].size();
        double w;
        for(int i=0;i<l;++i){
            w = adj[u][i].w;
            v = adj[u][i].v;
            if(du+w>=d[v]) continue;
            d[v] = du+w;
            q.push(node(v,d[v]));
        }
    }
}

inline void build(int from,point pt1){
    //剪枝:从from号点建边,之前的都不用考虑,因为一定不相交
    point pt2;
    //pt1为起点,pt2为终点
    for(int i=from+1;i<=n;++i){
        bool connect = true;
        pt2 = pt[i];
        for(int j=1;j<=wallCount;++j){
            //遍历所有墙,判断是否连通
            if(!intersect(pt1,pt2,wl[j])) continue;
            connect = false;
            break;
        }
        if(!connect) continue;
        adj[from].push_back(edge(i,dis(pt1.x,pt1.y,pt2.x,pt2.y)));
        ++m;
    }
}

int main(){
    scanf("%d",&n);
    wallCount = n*3;
    //墙的数量一定是n*3
    pt[1] = point(0,5); //起点
    int t = 2; //t记录当前节点数-1
    for(int i=1;i<=n;++i){
        scanf("%lf%lf%lf%lf%lf",&x,&a1,&b1,&a2,&b2);
        wl[(i-1)*3+1] = wall(x,10,b2);
        wl[(i-1)*3+2] = wall(x,a2,b1);
        wl[(i-1)*3+3] = wall(x,a1,0);
        pt[t] = point(x,a1);
        pt[t+1] = point(x,b1);
        pt[t+2] = point(x,a2);
        pt[t+3] = point(x,b2);
        t += 4;
    }
    pt[t] = point(10,5); //终点
    n = t;
    for(int i=1;i<n;++i) build(i,pt[i]);
    dijkstra();
    printf("%.2lf",d[n]);
}