洛谷P1354 房间最短路问题题解

题意：

在一个长宽均为 \(10\)，入口、出口分别为 \((0,5)\)、\((10,5)\) 的房间里，有几堵墙，每堵墙上有两个缺口，求入口到出口的最短路经。

输入格式：

第一排为 \(n\)（\(n \le 20\)），墙的数目。

接下来 \(n\) 排，每排 \(5\) 个实数 \(x,a_1,b_1,a_2,b_2\)。

\(x\) 表示墙的横坐标（所有墙都是竖直的），\(a_1 \sim b_1\) 和 \(a_2 \sim b_2\) 之间为空缺。

\(a_1,b_1,a_2,b_2\) 保持递增，\(x_1 \sim x_n\) 也是递增的。

输出格式：

输出最短距离，保留 \(2\) 位小数。

我们可以对端点暴力建图，但是这会有个问题，就是两个点之间可能无法直线连接。

由于题目中的路线不能是曲线之类的，因此我们只需要判断出这种情况，并且不连线就好了（~~什么大废话~~）

判断两点连线是否与某条直线相交，显然我们要知道它的方程，然后枚举每个可能的线。根据两点式方程： \[ \frac{y - y_2}{y_1-y_2} = \frac{x - x_2}{x_1-x_2} \Rightarrow y=\frac{y_2-y_1}{x_2-x_1}\left(x-x_1\right)+y_1 \] 时间复杂度 \(\mathcal{O}(n^3)\)

代码：（来自参考文献[1]）

#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 tmp1 = 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 tmp2 = k * tmp1 + b;
    return (tmp2 < y1 && tmp2 > y2 && pt1.x < tmp1 && pt2.x > tmp1);
}

void dijkstra()
{
    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]);
}