每個點有一個高度，從1到n使得最大高度和最小高度的差值最小，如果有相同高度，取路徑最短的。以前比賽的時候沒有去看，以為是很難的題，后來聽說要用二分，一直拖著，今天早上起來，讀了一下題目發(fā)現(xiàn)根本不用二分，點只有100個，可以對每個點的高度進(jìn)行上下界枚舉求最短路保存最優(yōu)值。這樣的話最壞復(fù)雜度是O(n^4)，這里n == 100，而且測試樣例有100組，但是這個題目的限制條件決定了有很多地方可以剪枝。首先，可以先將每個點的高度進(jìn)行升序排列，如果1或n不在所枚舉的高度上下界中，直接跳過。再者，如果當(dāng)前枚舉的高度差大于先前算出來的最優(yōu)值，直接跳過不算，最強(qiáng)的是：如果當(dāng)前能夠算出解，那么上界再大亦可算出，直接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);
}
}