题目意思 就是说 有一个起点一个终点 和一些虫洞，从一个虫洞进去然后出来，是不需要消耗时间的，注意点就是，虫洞是一条线段，你可以从线段的任意位置进去，从任意位置出来； 所以从一个虫洞到另一个虫洞的距离变成了空间的直线距离；
线段到线段的最短距离 用三分的方法
#include<iostream> #include<stdio.h> #include<cstring> #include<algorithm> #include<cmath> #define eps 1e-10 #define inf 0x1f1f1f1f using namespace std; int dcmp( double a ){ if( abs(a) < eps ) return 0; if(a > 0) return 1;return -1;} struct point{ double x,y,z; point(){} point( double x,double y,double z ):x(x),y(y),z(z){} }; typedef point Vector ; point operator + ( point a,point b ){ return point( a.x+b.x , a.y+b.y , a.z+b.z ); } point operator - ( point a,point b ){ return point( a.x-b.x , a.y-b.y, a.z-b.z ); } point operator * ( point a,double p ){ return point( a.x*p , a.y*p , a.z*p ); } point operator / ( point a,double p ){ return point( a.x/p , a.y/p , a.z/p ); } bool operator == ( point a,point b ){ if( dcmp(a.x-b.x) == 0&& dcmp(a.y-b.y) == 0 && dcmp(a.z-b.z) == 0 )return 1; return 0; } double Dot( point a,point b ){ return a.x*b.x + a.y*b.y + a.z*b.z; } double Length( point a ){ return sqrt(Dot(a,a));} double Angle( point a,point b ){ return acos(Dot(a,b))/Length(a)/Length(b); } // 点到 平面p0 - n 的距离；n 必须为单位向量 n 是平面法向量 double p_po_n( const point &p,const point &po,const point n ){ return abs(Dot( p-po,n )); } // 点在 平面p0 - n 的投影 ； n 必须为单位向量 n 是平面法向量 point p_po_n_jec( const point &p,const point &p0,const point &n ){ return p-n*Dot( p-p0,n ); } // 直线p1 p2 在平面 p0 - n 的交点，假设交点存在；唯一 point p_p_p( point p1,point p2,point p0,point n ){ point v = p2 - p1; double t = ( Dot(n,p0-p1)/Dot(n,p2-p1) ); return p1 + v*t; } point cross( point a,point b ){ return point( a.y*b.z - a.z*b.y, a.z*b.x - a.x*b.z,a.x*b.y - a.y*b.x ); } double area( point a,point b,point c ){ return Length(cross(b-a,c-a)); } double dis_to_line( point p, point a,point b ){ point v1 = b-a, v2 = p-a; return Length( cross(v1,v2)/Length(v1) ); } // p 到 ab 线段的距离 double dis_to_segm( point p,point a,point b ){ if( a == b )return Length(p-a); point v1 = b-a, v2 = p-a, v3 = p-b; if( dcmp( Dot(v1,v2) ) < 0 ) return Length(v2); else if( dcmp( Dot(v1,v3) ) > 0 ) return Length(v3); else return Length(cross(v1,v2))/Length(v1); } // 四面体的体积 double volume( point a,point b,point c,point d ){ return Dot( d-a,cross(b-a,c-a) ); } // 线段到线段的距离 double dis_l_to_l( point a,point b,point lt,point rt ) { while( abs(rt.x - lt.x) > eps || abs(rt.y - lt.y) > eps || abs( rt.z - lt.z) > eps ) { point temp; temp = lt + ( rt - lt )/3.0; point now; now = lt + ( rt - lt )/3.0*2.0; if( dis_to_segm(temp,a,b) < dis_to_segm(now,a,b) ) rt = now; else lt = temp; } return dis_to_segm( rt,a,b ); } point A[100],B[100]; double map[100][100]; double dis[100]; int que[200];bool vis[100]; void spfa( int N ) { int tail,hed; tail = hed = 0; for( int i = 0; i < 100; i++ )dis[i] = (1<<30); memset( vis,0,sizeof(vis) ); dis[0] = 0; que[tail++] = 0; vis[0] = true; while( tail > hed ) { int temp = que[hed++]; vis[temp] = false; for( int i = 0; i <= N; i++ ) if( dis[temp] + map[temp][i] < dis[i] ) { dis[i] = dis[temp] + map[temp][i]; if( !vis[i] ) { que[tail++] = i; vis[i] = true; } } } } int main( ) { int T,N; scanf("%d",&T); while( T-- ) { scanf("%d",&N); scanf("%lf%lf%lf",&A[0].x,&A[0].y,&A[0].z); scanf("%lf%lf%lf",&A[N+1].x,&A[N+1].y,&A[N+1].z); for( int i = 1; i <= N; i++ ) { scanf("%lf%lf%lf",&A[i].x,&A[i].y,&A[i].z); scanf("%lf%lf%lf",&B[i].x,&B[i].y,&B[i].z); } for( int i = 0; i <= N+1; i++ ) for( int j = 0; j <= N+1; j++ ) map[i][j] = (1<<30); map[0][N+1] = map[N+1][0] = Length( A[0]-A[N+1] ); for( int i = 1; i <= N; i++ ){ map[i][0] = map[0][i] = dis_to_segm( A[0],A[i],B[i] ); map[i][N+1] = map[N+1][i] = dis_to_segm( A[N+1],A[i],B[i] ); } for( int i = 1; i <= N; i++ ) for( int j = i+1; j <= N; j++ ){ map[i][j] = dis_l_to_l( A[i],B[i],A[j],B[j] ); map[j][i] = map[i][j]; } spfa( N + 1 ); printf("%.15lf ",dis[N+1]); } return 0; }