題目大意：
小明從家裡走到學校去考試， 路上有各個交叉點，它們有自己的海拔高度。 小明從家裡走到學校的路上，必然會經過不同的交叉點，因此會不斷的走上走下，忐忐忑忑，這讓他很不安，會影響他考試的發揮。因此，他要選擇一條起伏最小的路去學校。所謂的“起伏最小”，是指這條路上海拔最高的點與海拔最低的點的差值最小。
在起伏最小的前提下，還要求出路程距離最短。
分析與總結：
這題讓我想起以前做過的一題，HDU1598 ，不過那時是用最小生成樹做的，而且那題只需要輸出最小差而不用求最短路。
這題中，根據高度差的遞增，明顯滿足條件的路徑數量也是遞增的，因此可以二分“高度差”。
光有“高度差”還是不夠的，因為“起伏值”等於最大高度減最小高度， 所以需要再枚舉最小高度(下限low)， 在根據最小高度+“高度差”得到最大高度(上限up)， 有了low和up這兩個條件，就可以進行求限制最短路。
做這題WA了有20+， 因為在求最短路時沒有排除掉超過“上限”的邊。
之後試著最小生成樹的方法做了下，先求出“最小差”和上限與下限，然後再求最短路，但是WA了，糾結中...
代碼：
二分+枚舉+最短路
[cpp]
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int INF = 0x7fffffff;
const int VN = 120;
const int EN = 10005;
int n;
int m;
int size;
int head[VN];
int h[VN];
int order[VN];
int d[VN];
int up; // 上界
int low; // 下界
bool inq[VN];
struct Edge{
int v,next;
int w;
}E[EN];
void addEdge(int u,int v,int w){
E[size].v=v;
E[size].w=w;
E[size].next=head[u];
head[u]=size++;
}
int SPFA(int src){
memset(inq, 0, sizeof(inq));
for(int i=0; i<=n; ++i)d[i]=INF;
d[src]=0;
if(h[src]<low || h[src]>up) return INF; // 起點不符合條件直接返回INF
queue<int>q;
q.push(src);
while(!q.empty()){
int u=q.front(); q.pop();
if(h[u]<low || h[u]>up) continue; // 排除符合和限制的
inq[u] = false;
for(int e=head[u]; e!=-1; e=E[e].next)if(h[E[e].v]>=low&&h[E[e].v]<=up){//有限制
int tmp=d[u]+E[e].w;
if(d[E[e].v] > tmp){
d[E[e].v] = tmp;
if(!inq[E[e].v]){
inq[E[e].v]=true;
q.push(E[e].v);
}
}
}
}
return d[n];
}
int main(){
int T, u, v;
int len, Min, Max;
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
size=0;
memset(head, -1, sizeof(head));
for(int i=1; i<=n; ++i){
scanf("%d", &h[i]);
order[i]=h[i];
if(h[i]<Min)Min=h[i];
if(h[i]>Max)Max=h[i];
}
for(int i=0; i<m; ++i){
scanf("%d%d%d",&u,&v,&len);
addEdge(u,v,len);
addEdge(v,u,len);
}
sort(order+1, order+1+n);
int left=0, right=Max-Min+1, mid;
int ans, dif=INF, minlen=INF;
while(left < right){ // 二分“高度差”
mid = (left+right)>>1;
bool flag=false;
for(int i=1; i<=n; ++i){ // 枚舉最低海拔
low=order[i];
up=order[i]+mid; // 得到海拔上限
int tmp=SPFA(1);
if(tmp!=INF){
flag=true;
ans=tmp;
break;
}
}
if(flag){
right=mid;
if(mid<dif){
dif=mid;
minlen=ans;
}
else if(mid==dif && ans<minlen){
minlen=ans;
}
}
else{
left=mid+1;
}
}
printf("%d %d\n", dif, minlen);
}
return 0;
}
