题解：最短路径穿过障碍墙（Mid-Central USA 1996）

一、题目分析

本题要求计算从点(0,5)到点(10,5)穿过障碍墙的最短路径。关键条件：

• 障碍墙为垂直墙，位于0 < x < 10之间
• 每面墙有两个门，由四个y坐标定义
• 路径不能穿过墙，但可以经过门的端点
• 需要精确到小数点后两位

二、解题思路

1. 建模：
   将起点、终点和所有门的端点视为图中的节点，若两点间的线段不穿过任何墙，则连边，边权为欧几里得距离。

2. 算法选择：
   使用Dijkstra算法计算最短路径，需预处理所有合法边。

3. 线段相交判断：
   对于任意两点间的线段，检查是否与所有墙的非门部分相交。

三、代码解析

#include<queue>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;

struct dot {
    double x, y; int br;  // br表示该点所属的墙编号
};

dot a[8002], seg[5002][6];  // a存储所有点，seg存储墙的线段
int n, m;  // n为墙的数量，m为点的数量
double pl, x, y, xx, yy;
const double eps = 1e-8;  // 浮点误差
const double INF = 0x3f3f3f3f;  // 无穷大

// 图的邻接表结构
struct node {
    double x;  // 边权
    int to, nxt;  // 终点和下一条边
};
node e[300001];
int le[8002], KK;  // 邻接表头指针和边计数器
double dis[8002];  // 最短距离

// 向量运算重载
dot operator +(dot x, dot y) { return (dot){x.x + y.x, x.y + y.y, -1}; }
dot operator -(dot x, dot y) { return (dot){x.x - y.x, x.y - y.y, -1}; }
double operator *(dot x, dot y) { return x.x * y.x + x.y * y.y; }  // 点积
double operator ^(dot x, dot y) { return x.x * y.y - x.y * y.x; }  // 叉积

// 计算两点间距离
double get_dis(dot x, dot y) {
    return sqrt((x - y) * (x - y));
}

// 判断两线段是否相交（不包括端点）
bool check_meet(dot A, dot B, dot C, dot D) {
    dot CA = A - C, CB = B - C, DA = A - D, DB = B - D;
    if ((CA ^ CB) * (DA ^ DB) < eps) return 1;  // 跨立实验
    return 0;
}

// 检查两点间线段是否不穿过任何墙
bool check(dot x, dot y) {
    for (int i = x.br + 1; i <= y.br - 1; i++) {  // 枚举中间的墙
        for (int j = 0; j <= 4; j += 2) {  // 检查墙的每个非门部分
            if (check_meet(x, y, seg[i][j], seg[i][j + 1])) return 0;
        }
    }
    return 1;
}

// 添加无向边
void add(int x, int y, double z) {
    e[++KK] = (node){z, y, le[x]}; le[x] = KK;
    e[++KK] = (node){z, x, le[y]}; le[y] = KK;
}

// Dijkstra算法求最短路径
double Dij(int s, int t) {
    memset(in, 0, sizeof(in));
    for (int i = 1; i <= m; i++) dis[i] = INF;
    while (!Q.empty()) Q.pop();
    dis[s] = 0; Q.push(make_pair(0, s));
    
    while (!Q.empty()) {
        int now = Q.top().second; Q.pop();
        if (in[now]) continue;
        in[now] = 1;
        
        for (int i = le[now]; i; i = e[i].nxt)
            if (e[i].x + dis[now] < dis[e[i].to]) {
                dis[e[i].to] = dis[now] + e[i].x;
                Q.push(make_pair(dis[e[i].to], e[i].to));
            }
    }
    
    return dis[t];
}

int main() {
    scanf("%d", &n);
    while (n != -1) {
        m = 0;
        a[++m] = (dot){0, 5, 0};  // 起点
        
        // 读入每面墙的信息
        for (int i = 1; i <= n; i++) {
            scanf("%lf", &x);
            seg[i][0] = (dot){x, 0, -1};  // 墙的底部
            
            // 读入门的端点
            for (int j = 1; j <= 4; j++) {
                scanf("%lf", &y);
                seg[i][j] = (dot){x, y, -1};
                a[++m] = (dot){x, y, i};  // 保存门的端点
            }
            
            seg[i][5] = (dot){x, 10, -1};  // 墙的顶部
        }
        
        a[++m] = (dot){10, 5, n + 1};  // 终点
        
        // 建图：初始化邻接表
        memset(le, 0, sizeof(le));
        KK = 0;
        
        // 枚举所有点对，添加合法边
        for (int i = 1; i <= m - 1; i++)
            for (int j = i + 1; j <= m; j++) {
                if (a[i].br == a[j].br) continue;  // 同一边墙上的点不连边
                if (a[j].br - a[i].br == 1 || check(a[i], a[j]))  // 相邻墙或不穿过墙的点对
                    add(i, j, get_dis(a[i], a[j]));
            }
        
        // 计算并输出最短路径
        printf("%.2f\n", Dij(1, m));
        
        scanf("%d", &n);  // 读入下一组数据
    }
    
    return 0;
}

四、关键步骤解析

1. 输入处理与点的存储

   • 起点(0,5)和终点(10,5)分别标记为墙0和墙n+1
   • 每面墙的门端点保存为图中的节点，并记录所属墙编号

2. 线段相交判断

   • 使用叉积进行跨立实验，判断两线段是否相交
   • 检查两点间线段是否穿过任何墙的非门部分

3. 图的构建

   • 若两点间线段不穿过任何墙，则添加边，边权为欧几里得距离
   • 相邻墙的点自动连边（无需检查相交）

4. 最短路径计算

   • 使用Dijkstra算法计算起点到终点的最短路径
   • 优先队列优化时间复杂度至O((V+E)logV)

五、示例解析

对于输入：

2
4 2 7 8 9
7 3 4.5 6 7

1. 点的构建：

   • 起点：(0,5)
   • 第一面墙(4)：门端点(4,2)、(4,7)、(4,8)、(4,9)
   • 第二面墙(7)：门端点(7,3)、(7,4.5)、(7,6)、(7,7)
   • 终点：(10,5)

2. 合法边的构建：

   • 起点与第一面墙的可达端点连边
   • 相邻墙之间的可达端点连边
   • 第二面墙与终点连边

3. 最短路径计算：
   通过Dijkstra算法找到最优路径

六、注意事项

1. 浮点精度

   • 线段相交判断中，端点相交不视为相交

2. 输出格式

   • 结果保留两位小数，不足补零

3. 复杂度分析

   • 点的数量：O(n)，n为墙的数量（最多18）
   • 边的数量：O(n²)
   • 总时间复杂度：O(n² log n)，可处理较大数据

七、可能的优化

1. 预处理优化

   • 按x坐标排序墙，减少线段相交判断范围

2. 剪枝策略

   • 对于明显不可达的点对，提前排除

3. 线段相交判断优化

   • 使用区间判断替代叉积，提高效率