解题思路

整体思路概述

本题的目标是计算印第安纳·琼斯为了从初始所在墙壁段到达被困者所在墙壁段，所需携带的木板的最小长度。解题的核心在于利用 Dijkstra 算法进行路径搜索，同时需要处理墙壁之间距离的计算，通过不断尝试不同的木板长度，找到满足条件的最小长度。

具体步骤

1. 数据结构定义

   • struct wall：用于存储每段墙壁的信息，包含墙壁起始点的坐标 (x, y) 以及长度和方向信息 l。
   • struct node：用于 Dijkstra 算法中的优先队列，存储当前所在墙壁段的编号 p 和从起点到该墙壁段的最大木板长度 d。

2. 距离计算函数

   • dis 函数：计算两点 (x1, y1) 和 (x2, y2) 之间的欧几里得距离。
   • walldis 函数：计算两段墙壁之间的最短距离，需要根据墙壁的方向（东西走向或南北走向）进行不同情况的处理：
     • 若两段墙壁都是点（l = 0），直接计算两点间的距离。
     • 对于不同走向的墙壁组合，需要考虑墙壁的端点和重叠情况，分多种情况计算最短距离。

3. Dijkstra 算法

   • dijk 函数：使用 Dijkstra 算法进行路径搜索，优先队列 q 按照木板长度从小到大排序。
   • 初始化 d 数组为 -1，表示所有墙壁段未被访问。
   • 从起点开始，不断从优先队列中取出当前木板长度最小的墙壁段，若该墙壁段未被访问过，则更新其距离 d，并将其相邻且距离小于等于当前尝试的木板长度 thre 的墙壁段加入优先队列。
   • 若到达终点，则返回从起点到终点的最大木板长度。

4. 主函数逻辑

   • 读取输入的墙壁段数量 n 和每段墙壁的信息。
   • 确定起点 st 和终点 ed。
   • 计算起点和终点之间的初始木板长度 dthr，并调用 dijk 函数进行路径搜索。
   • 输出结果，保留两位小数。

#include<iostream>
#include<cmath>
#include<queue>
#include<iomanip>
using namespace std;

struct wall{
       int x,y,l;
}w[1000];

float dis(int x1, int y1, int x2, int y2){
       return sqrt((double)((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)));
}

int n,st,ed; 
float d[1000];

struct node{
       int p;
       float d;
       node(int a, float b):p(a), d(b){}
};

bool operator<(const node &a, const node &b){
     return a.d>b.d;
}

float walldis(int a, int b){
       if(w[a].l==0&&w[b].l==0) return dis(w[a].x,w[a].y,w[b].x,w[b].y);
       if(w[a].l>=0) swap(a,b);
       int x1 = w[a].x, y1 = w[a].y, x2 = x1, y2 = y1, x3 = w[b].x, y3 = w[b].y, x4 = x3, y4 = y3;
       
       if(w[b].l>=0){
                    x4 += w[b].l;
                    if(w[a].l>=0){
                                  x2 += w[a].l;
                                  if(x2>=x3&&x1<=x4)
                                                    return max(y1-y3,y3-y1);
                                  else
                                      return min(dis(x2,y2,x3,y3),dis(x4,y4,x1,y1));
                    }
                    else{
                         y2 += -w[a].l;
                         if(x1>=x3&&x1<=x4){
                                            if(y3>=y1&&y3<=y2) return 0;
                                            return min(y1-y3>0?y1-y3:y3-y1,y2-y3>0?y2-y3:y3-y2);
                         }
                         else if(y3>=y1&&y3<=y2)
                              return min(x1-x3>0?x1-x3:x3-x1,x1-x4>0?x1-x4:x4-x1);
                         else if(y3<y1)
                              return min(dis(x3,y3,x1,y1),dis(x4,y4,x1,y1));
                         else
                             return min(dis(x3,y3,x2,y2),dis(x4,y4,x2,y2));
                    }
       }
       else{
            y4 -=w[b].l, y2 -= w[a].l;
            if(y2>=y3&&y4>=y1)
                              return max(x1-x3,x3-x1);
            else if(y2<y3)
                 return dis(x2,y2,x3,y3);
            else
                return dis(x1,y1,x4,y4);
       }
}



float dijk(float thre){
       priority_queue<node> q;
       for(int i = 0; i < n; i++)
               d[i] = -1;
               
       st = 0;
       q.push(node(st,0));
       while(!q.empty()){
                         node t = q.top();
                         q.pop();
                         
                         int p = t.p;
                         float dd = t.d;
                         if(d[p]>=0) continue;
                         if(p==ed)
                                  return dd;
                         
                         d[p] = dd;
                         for(int i = 0; i < n; i++)
                                 if(d[i]<0){
                                            float newd = walldis(p,i);
                                            if(newd<=thre)
                                                         q.push(node(i,max(newd,dd)));
                                 }
       }
       return -1;
}
                         

int main(){
    while(cin>>n&&n){
                     for(int i = 0; i < n; i++)
                             cin >> w[i].x >> w[i].y >> w[i].l;
                     
                     st = 0, ed = 1;
                     float dthr = walldis(st,ed), res = dijk(dthr);
                     cout << setiosflags(ios::fixed) << setprecision(2) << res << endl;
    }
}