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

4 4

1 2 2

2 3 4

1 4 1

3 4 2

2

1 3

1 2

1

0
解题分析：
由于数据范围很小，所以可以先将所有边排序，然后枚举最小边，然后按顺序枚举最大边，每次枚举的时候都判断一下起点和终点是否连通(用并查集判断)，如果联通了，就更新一下最大、最小边权之差。

#include <cstdio>

#include <algorithm>

using namespace std;

#define INF 0x3f3f3f3f

#define M 205

struct EDGE{

    int x,y,val;

}edge[];

int father[M],n,m;

void init(){

    for(int i=;i<=n;i++)father[i]=i;

}

int find(int x){

    if(father[x]==x)return x;

    father[x]=find(father[x]);

    return father[x];

}

bool cmp(EDGE a,EDGE b){

    return a.val<b.val;

}

int main(){

    while(scanf("%d%d",&n,&m)!=EOF){

        for(int i=;i<=m;i++)scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].val);

        sort(edge+,edge++m,cmp);

        int q;scanf("%d",&q);

        while(q--){

            int s,e;scanf("%d%d",&s,&e);

            mn=INF;

            for(int i=;i<=m;i++){  //枚举最小边

                init();

                bool fp=false;

                for(int j=i;j<=m;j++){    //寻找最大边

                    int f1=find(edge[j].x);

                    int f2=find(edge[j].y);

                    if(f1!=f2){

                        father[f2]=f1;

                    }

                    if(find(s)==find(e)){   //判断起点与终点是否连通

                        fp=true;

                        mn=min(mn,edge[j].val-edge[i].val);    //更新最大、最小边权之差

                    }

                }

                if(!fp)break;  //如果从第i条边开始，即使连上了所有边也不能使起点、终点连通，就直接跳出，因为后面从i+1,i+2开始的所有边连接后也不能使起点、终点连通

            }

            if(mn==INF)printf("-1\n");

            else printf("%d\n",mn);

        }

    }

    return ;

}

2018-10-07