题目链接：

思路：不知道怎么回事，wa了n多次，然后不知道怎么回事就过了==，还是简单的说一下思路吧：一次以起点为源点跑一遍spfa，然后以终点为起点跑一次spfa,这样我们就可以枚举difficult为maxdist的边了,设该边的端点为x,y,于是有ans=min(ans,dist1[x]+Get_Dist(x,y)+dist2[y]）。

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 #include
            
              8 using namespace std; 9 typedef pair
             
              Pair; 10 #define MAXN 44444 11 #define inf 1e16 12 double dist1[MAXN],dist2[MAXN]; 13 bool mark[MAXN]; 14 struct Edge{ 15 int v; 16 double w; 17 Edge(){} 18 Edge(int _v,double _w){ 19 v=_v,w=_w; 20 } 21 }; 22 vector
              
               map1[MAXN],map2[MAXN]; 23 vector
               
                vet; 24 struct Point{ 25 int x,y,z; 26 }point[MAXN]; 27 28 struct Node{ 29 int vs,vt; 30 }node[MAXN]; 31 int n,m,st,ed,maxdist; 32 33 double Get_Dist(int vs,int vt){ 34 double xx=1.0*(point[vs].x-point[vt].x)*(point[vs].x-point[vt].x); 35 double yy=1.0*(point[vs].y-point[vt].y)*(point[vs].y-point[vt].y); 36 double zz=1.0*(point[vs].z-point[vt].z)*(point[vs].z-point[vt].z); 37 return sqrt(xx+yy+zz); 38 } 39 40 int Get(int vs,int vt){ 41 if(point[vs].z
                
                 map[],double dist[]) 51 { 52 memset(mark,false,(n+2)*sizeof(mark[0])); 53 for(int i=1;i<=n;i++)dist[i]=inf; 54 dist[st]=0;mark[st]=true; 55 queue
                 
                  Q; 56 Q.push(st); 57 while(!Q.empty()){ 58 int u=Q.front(); 59 Q.pop(); 60 mark[u]=false; 61 for(int i=0;i