不是自己写的代码，但是帮忙d了挺久...
很直观的想法，如果把起点，终点，和所有的墙的边界点看作点的话，最终的最短路径一定只经过这些点，把图建出来，跑一边最短路即可。
1 #include<cstdio> 2 #include<queue> 3 #include<iostream> 4 #include<cstring> 5 #include<algorithm> 6 #include<cmath> 7 using namespace std; 8 #define maxn 50000 9 const double inf=99999999.; 10 priority_queue<pair<double,int> > Q; 11 struct node 12 { 13 double x; 14 double y[10]; 15 } p[maxn]; 16 int head[maxn],to[maxn],nxt[maxn]; 17 double w[maxn],dis[maxn]; 18 bool vis[maxn]; 19 int n,tot,cnt; 20 void add(int a,int b,double val) 21 { 22 to[++cnt]=b; 23 nxt[cnt]=head[a]; 24 head[a]=cnt; 25 w[cnt]=val; 26 } 27 bool check(double x,double y,int now,int to,int whi) 28 { 29 if(to-now<=1) return 1; 30 double k=(p[to].y[whi]-y)/(p[to].x-x); 31 double B=y-k*x; 32 33 for(int i=now+1; i<=to-1; i++) 34 { 35 double ny=k*p[i].x+B; 36 if(ny>p[i].y[3]||ny<p[i].y[0]||(ny>p[i].y[1]&&ny<p[i].y[2])) 37 return 0; 38 } 39 return 1; 40 } 41 double find(double x,double y,double a,double b) 42 { 43 return sqrt((x-a)*(x-a)+(y-b)*(y-b)); 44 } 45 void solve() 46 { 47 for(int i=1; i<=tot; i++) 48 { 49 for(int j=0; j<=3; j++) 50 { 51 if(check(0,5,0,i,j)) 52 { 53 if(p[i].x==0) continue; 54 add(0,(i-1)*4+j+1,find(0,5,p[i].x,p[i].y[j])); 55 } 56 } 57 } 58 for(int i=1; i<=tot; i++) 59 for(int o=0; o<=3; o++) 60 for(int j=i+1; j<=tot; j++) 61 for(int k=0; k<=3; k++) 62 if(check(p[i].x,p[i].y[o],i,j,k)) 63 { 64 if(p[i].x==p[j].x) continue; 65 add((i-1)*4+o+1,(j-1)*4+k+1,find(p[i].x,p[i].y[o],p[j].x,p[j].y[k])); 66 } 67 } 68 void DJ() 69 { 70 dis[0]=0; 71 Q.push(make_pair(0,0)); 72 while(!Q.empty()) 73 { 74 int u=Q.top().second; 75 Q.pop(); 76 if(vis[u]||dis[u]==inf) continue; 77 vis[u]=1; 78 for(int i=head[u]; i; i=nxt[i]) 79 { 80 int v=to[i]; 81 if(dis[v]>dis[u]+w[i]) 82 { 83 dis[v]=dis[u]+w[i]; 84 Q.push(make_pair(-dis[v],v)); 85 } 86 } 87 } 88 } 89 int main() 90 { 91 scanf("%d",&n); 92 for(int i=0; i<=n*4+1; i++) 93 dis[i]=inf; 94 for(int i=1; i<=n; i++) 95 { 96 double x,a,b,c,d; 97 scanf("%lf%lf%lf%lf%lf",&x,&a,&b,&c,&d); 98 p[++tot].x=x; 99 p[tot].y[0]=a; 100 p[tot].y[1]=b; 101 p[tot].y[2]=c; 102 p[tot].y[3]=d; 103 } 104 p[++tot].x=10; 105 for(int i=1; i<=3; i++) p[tot].y[i]=99999999.9; 106 p[tot].y[0]=5; 107 solve(); 108 DJ(); 109 printf("%.2lf ",dis[4*n+1]); 110 return 0; 111 }