说实话，一看到这个题，我第一反应就是dfs，本来想用dfs搜索每一个可行的路径，然后记录每一个可行路径上的最小速度差，然后再找出最小。可是写着写着就写不下去了，因为记录路径实在不会。在网上看别人的方法，才恍然大悟，原来并查集是可以的。好一个经典的算法啊。
思路：就是先按速度由小到大排序，然后在合并不在一个集合的元素，并检查起始点是否在一个集合里，如果已经在一个集合里了，那么用这时的速度减去开始合并进来的那个速度，则这个值就是所要求解的值，当然还有没有找到的情况，这个很好考虑了就
1 #include<stdio.h>
2 #include<string.h>
3 #include<iostream>
4 #include<algorithm>
5 using namespace std;
6 #define inf 999999999
7 #define N 250
8 int a[N];
9 int n,m;
10 struct node
11 {
12 int x,y,dis;
13 }f[1010];
14 int cmp(node c,node d)
15 {
16 return c.dis<d.dis;
17 }
18 int find(int x)
19 {
20 if(a[x]!=x)
21 return a[x]=find(a[x]);
22 return a[x];
23 }
24 int main()
25 {
26 int i,j;
27 int h;
28 while(cin>>n>>m)
29 {
30 for(i=0;i<m;i++)
31 cin>>f[i].x>>f[i].y>>f[i].dis;
32 sort(f,f+m,cmp);
33 int q,s,e;
34 cin>>q;
35 while(q--)
36 {
37 cin>>s>>e;
38 int k=inf,ans;
39 for(i=0;i<m;i++)
40 {
41 for(h=1;h<=n;h++)
42 a[h]=h;
43 for(j=i;j<m;j++)
44 {
45 int root1=find(f[j].x);
46 int root2=find(f[j].y);
47 if(root1!=root2) a[root1]=root2;
48 if(find(s)==find(e))
49 {
50 ans=f[j].dis-f[i].dis;
51 if(ans<k) k=ans;
52 break;
53 }
54
55 }
56 if(j==m) break;
57 }
58 if(k!=inf) cout<<k<<endl;
59 else cout<<"-1"<<endl;
60 }
61 }
62 return 0;
63 }