Problem Description

XX星有许多城市，城市之间通过一种奇怪的高速公路SARS(Super Air Roam Structure—超级空中漫游结构）进行交流，每条SARS都对行驶在上面的Flycar限制了固定的Speed，同时XX星人对 Flycar的“舒适度”有特殊要求，即乘坐过程中最高速度与最低速度的差越小乘坐越舒服 ,(理解为SARS的限速要求，flycar必须瞬间提速/降速，痛苦呀 ),
但XX星人对时间却没那么多要求。要你找出一条城市间的最舒适的路径。(SARS是双向的）。

Input

输入包括多个测试实例，每个实例包括：
第一行有2个正整数n (1<n<=200)和m (m<=1000),表示有N个城市和M条SARS。
接下来的行是三个正整数StartCity,EndCity,speed,表示从表面上看StartCity到EndCity,限速为speedSARS。speed<=1000000
然后是一个正整数Q（Q<11),表示寻路的个数。
接下来Q行每行有2个正整数Start,End, 表示寻路的起终点。

Output

每个寻路要求打印一行，仅输出一个非负整数表示最佳路线的舒适度最高速与最低速的差。如果起点和终点不能到达，那么输出-1。

Sample Input

4 4
1 2 2
2 3 4
1 4 1
3 4 2
2
1 3
1 2

Sample Output

1
0

分析

最小差值生成树怎么找呢？首先我们明确，最小差值生成树不等于最小生成树。最小生成树保证的只是权值和最小。随便画个图看看。

如图，最小差值是0，而按最小生成树，其差值是1。
所以最小差值生成树到底咋求？
注意到数据范围，复杂度可能是 O ( q ∗ m 2 ) O(q*m^2) O(q∗m2)，我们可以枚举生成树的最小边 j j j ，再生成一颗树。
而这棵树就是在以 j j j 为最小边的最小差值生成树。证明方法和克鲁斯卡尔很相似。假如有更小的最大边，那么加上它之后会形成一个环，而它比最大边要小，我们在枚举到它这条边的时候（这时候还没有枚举到最大边）显然就会把它连通。而事实上我们并没有把它连通，因此不存在更小的最大边。

代码如下

#include <bits/stdc++.h>
#define inf 2147483647
using namespace std;
struct node{
	int a, b, c;
	bool operator < (const node & A) const{
		return c < A.c;
	}
}d[1005];
int f[205];
int find(int x){
	return x == f[x]? x: f[x] = find(f[x]);
}
int main(){
	int i, j, n, m, q, u, v, a, b, c, ans;
	while(scanf("%d%d", &n, &m) != EOF){
		for(i = 1; i <= m; i++) scanf("%d%d%d", &d[i].a, &d[i].b, &d[i].c);
		sort(d + 1, d + i);
		scanf("%d", &q);
		while(q--){
			ans = inf;
			scanf("%d%d", &u, &v);
			for(i = 1; i <= m; i++){
				for(j = 1; j <= n; j++) f[j] = j;
				for(j = i; j <= m; j++){
					a = find(d[j].a); b = find(d[j].b);
					if(a != b) f[a] = b;
					if(find(u) == find(v)){
						ans = min(ans, d[j].c - d[i].c);
						break;
					}
				}
			}
			if(ans < inf) printf("%d\n", ans);
			else printf("-1\n");
		}
	}
	return 0;
}