每个点有一个高度，从1到n使得最大高度和最小高度的差值最小，如果有相同高度，取路径最短的。以前比赛的时候没有去看，以为是很难的题，后来听说要用二分，一直拖着，今天早上起来，读了一下题目发现根本不用二分，点只有100个，可以对每个点的高度进行上下界枚举求最短路保存最优值。这样的话最坏复杂度是O(n^4)，这里n == 100，而且测试样例有100组，但是这个题目的限制条件决定了有很多地方可以剪枝。首先，可以先将每个点的高度进行升序排列，如果1或n不在所枚举的高度上下界中，直接跳过。再者，如果当前枚举的高度差大于先前算出来的最优值，直接跳过不算，最强的是：如果当前能够算出解，那么上界再大亦可算出，直接break；
代码如下：
#include <iostream>
#include <algorithm>
using namespace std;
int t;
int alti[101];
int n, m;
int d[101], s[101];
int map[101][101];
int sor[101];
int Dijkstra(int Min, int Max) 
{
int i;
for(i = 1; i <= n; i++) {
if(alti[i] > Max || alti[i] < Min) {
d[i] = 100000000;
s[i] = 0;
}else {
d[i] = map[1][i];
s[i] = 0;
}
}
d[1] = 0;
s[1] = 1;
while(1) {
int Mina = 100000000, u = -1;
for(i = 1; i <= n; i++) {
if(alti[i] > Max || alti[i] < Min)
continue;
if(!s[i] && d[i] < Mina) {
Mina = d[i];
u = i;
}
}
if(u == n)
return d[u];
if(u == -1)
return -1;
s[u] = 1;
for(i = 1; i <= n; i++) {
if(alti[i] > Max || alti[i] < Min)
continue;
if(!s[i] && d[u] + map[u][i] < d[i]) {
d[i] = d[u] + map[u][i];
}
}
}
}
int main() {
int i, j;
scanf("%d", &t);
int a, b, c;
while(t--) {
scanf("%d %d", &n, &m);
for(i = 1; i <= n; i++) {
for(j = 1; j <= n; j++) {
map[i][j] = 100000000;
}
}
for(i = 1; i <= n; i++) {
scanf("%d", &alti[i]);
sor[i-1] = alti[i];
}
sort(sor, sor + n);
while(m--){
scanf("%d %d %d", &a, &b, &c);
if(c < map[a][b]) {
map[a][b] = map[b][a] = c;
}
}
int Min = 2000000000, path;
for(i = 0; i < n; i++) {
for(j = i+1; j < n; j++) {
if(alti[n] > sor[j] || alti[n] < sor[i])
continue;
if(alti[1] > sor[j] || alti[1] < sor[i])
continue;
if(sor[j] - sor[i] > Min)
break;
int yu;
yu = Dijkstra(sor[i], sor[j]);
//printf("%d %d %d\n", sor[i], sor[j], yu);
if(yu + 1 && sor[j] - sor[i] == Min) {
if(yu < path)
path = yu;
}
if(yu + 1 && sor[j] - sor[i] < Min) {
Min = sor[j] - sor[i];
path = yu;
}
if(yu != -1)
break;
}
}
if(n == 1)
printf("0 0\n");
else
printf("%d %d\n", Min, path);
}
}