给你一个图，有边权，K个询问：u到v 的路径中 边权最大值-边权最小值的最小值是多少
http://acm.hdu.edu.cn/showproblem.php?pid=1598
题解（非自己想出）：把边排序 枚举最小边，然后类似克洛斯卡尔，不断加边 更新ANS值（F[i][j]） 复杂度Q*E^2
如果Q变大 可以选择 E*E*N 预处理所有点
为何我自己没想到？：太拘泥于用深搜的想法去解决，这种跟边权最大值最小值的题目应该多考虑排序边
解法2：
二分差值，枚举最小边，再克鲁斯卡尔
复杂度（Q*log(max-min)*E*E）
复杂度显然不如 解法1
代码：
/*
WA1:忘记不能到达输出-1
*/
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#define oo 0x13131313
using namespace std;
struct Edge
{
int s,t,w;
};
int n,m;
Edge A[1100];
int father[300];
void init()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
}
void input()
{
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&A[i].s,&A[i].t,&A[i].w);
}
}
void Clear()
{
for(int i=1;i<=299;i++)
father[i]=i;
}
bool cmp(Edge a,Edge b)
{
return a.w<b.w;
}
int find(int x)
{
if(x!=father[x])
father[x]=find(father[x]);
return father[x];
}
void Union(int a,int b)
{
int aa=find(a),bb=find(b);
father[aa]=bb;
}
void solve()
{
sort(A+1,A+m+1,cmp);
int Q,u,v;
cin>>Q;
for(int k=1;k<=Q;k++)
{
cin>>u>>v;
int ok=0;
int ans=100000000;
for(int i=1;i<=m;i++)
{
Clear();
for(int j=i;j<=m;j++)
{
Union(A[j].s,A[j].t);
if(find(u)==find(v)) {
ans=min(ans,A[j].w-A[i].w);
break;
}
}
}
if(ans==100000000) printf("-1
");
else printf("%d
",ans);
}
}
int main()
{
// init();
while(cin>>n>>m)
{
input();
solve();
}
}