**(1) 二分

    把所有的高度都拿过来,组合起来,sort一遍,然后二分,找到能连通的最小的那个,但这里存在一起情况,就是遇到高度差相等的时候会bug….

(2) 枚举 连通直接break

    把所有的高度都拿过来,组合起来,soet一遍,然后暴力枚举上下限制,能连通直接break;这个显然是错的,直接break的话只能保证高度差最小,不能保证路径最短..

(3) 枚举 连通并且高度变化的时候 break;就是在(2)的基础上不直接break,如果第一次找到能连接1,n的路径直接记录当前高度差,然后一直往后跑到高度差不等于第一次连通的高度差的时候break;这样做肯定是对的,但是时间复杂度我感觉过不去….

(4) 写到第三部我突然想到一个自己感觉正确的方法,因为手懒就不写那个代码了,直接说思路,就是hash + 二分,我们枚举出所有范围组合的后排序,排序后吧所有高度差相同的hash成一个点,每次如果这个点中的某一个点使其连通了,那么这个点就是可行点(如果多个都满足记得保留最优),直接mid = up = mid - 1…….,感觉这样应该会好点..虽然没有去实现,感觉会优化很多时间吧…

**

下面是(3)的代码,虽然ac了,但自认为会TLE..

#include
#include
#include
#include

#define N_node 100 + 20
#define N_edge 10000 + 500
#define INF 2000000000
using namespace std**;

typedef struct
{
int** to ,next ,cost; }STAR**;

typedef struct
{
int** low ,up ,d; }HHH;

STAR E[N_edge];
HHH DH[100*100+100]; int list[N_node] ,tot; int s_x[N_node]; int H[N_node**];

void** add(int a, int b ,int c) {
E[++tot].to = b;
E[tot].cost = c;
E[tot].next = list[a];
list[a] = tot**;
}

bool** camp(HHH a ,HHH b) { return a.d < b.d**;
}

int** abss(int x) { return x > 0 ? x : -x**;
}

void** SPFA(int s ,int n ,int low ,int up) { for(int i = 0 ;i <= n ;i ++)
s_x[i] = INF; int mark[N_node] = {0};
s_x[s] = 0;
mark[s] = 1;
queueq;
q.push(s); while(!q.empty()) { int tou ,xin;
tou = q.front();
q.pop();
mark[tou] = 0; for(int k = list[tou] ;k ;k = E[k].next) {
xin = E[k].to; if(H[xin] < low || H[xin] > up) continue; if(s_x[xin] > s_x[tou] + E[k].cost) {
s_x[xin] = s_x[tou] + E[k].cost; if(!mark[xin]) {
mark[xin] = 1;
q.push(xin**);
}
}
}
}
return ;
}

int main ()
{
int** t ,i ,j ,n ,m; int a ,b ,c;
scanf("%d" ,&t); while(t--) {
scanf("%d %d" ,&n ,&m); for(i = 1 ;i <= n ;i ++)
scanf("%d" ,&H[i]);
memset(list ,0 ,sizeof(list));
tot = 1; for(i = 1 ;i <= m ;i ++) {
scanf("%d %d %d" ,&a ,&b ,&c);
add(a,b,c);
add(b,a,c**);
}

  int** tmp **=** 0**;  
  for(**i **=** 1 **;**i **<=** n **;**i **++)  
  for(**j **=** i **+** 1 **;**j **<=** n **;**j **++)  
  {  
     int** low **=** H**\[**i**\] <** H**\[**j**\] ?** H**\[**i**\] :** H**\[**j**\];  
     int** up **=** H**\[**i**\] >** H**\[**j**\] ?** H**\[**i**\] :** H**\[**j**\];**  
     DH**\[++**tmp**\].**low **=** low**;**  
     DH**\[**tmp**\].**up **=** up**;**  
     DH**\[**tmp**\].**d **=** up **-** low**;  
  }**  
  sort**(**DH **+** 1 **,**DH **+** tmp **+** 1**,**camp**);

  int** minc **=** INF**,**minz **=** 0**;  
  for(**i **=** 1 **;**i **<=** tmp **;**i **++)  
  {  
     if(**H**\[**1**\] <** DH**\[**i**\].**low **||** H**\[**1**\] >** DH**\[**i**\].**up**) continue;  
     if(**H**\[**n**\] <** DH**\[**i**\].**low **||** H**\[**n**\] >** DH**\[**i**\].**up**) continue;**  
     SPFA**(**1 **,**n **,**DH**\[**i**\].**low **,**DH**\[**i**\].**up**);  
     if(**s\_x**\[**n**\] ==** INF**) continue;

     if(**minc **==** INF**)  
     {**  
        minc **=** DH**\[**i**\].**d**;**  
        minz **=** s\_x**\[**n**\];  
     }  
     else  
     {  
        if(**minc **!=** DH**\[**i**\].**d**) break;  
        if(**s\_x**\[**n**\] <** minz**)**  
        minz **=** s\_x**\[**n**\];  
     }  
  }  
  if(**n **==** 1**)** printf**(**"0 0\\n"**);  
  else** printf**(**"%d %d\\n" **,**minc **,**minz**);  

}
return** 0; }