http://acm.hdu.edu.cn/showproblem.php?pid=1598
如果普通做的话，很容易想到行不通，因为过程情况太多了，根本无法算出最大差，所以简化一些就是
让开始的点作为速度最小的点，结束的点作为速度最大的点，这样就可以马上求得舒适度了。
处理：将所有边按速度升序排序，用克鲁斯卡尔加边，当起点s和终点e的根为一个根是则证明连通，此时舒适度就是起点终点的速度差。这样将所有情况枚举一遍找最小值即可，当第一遍枚举没找到答案的话，后面的情况就不用枚举了，因为第一种情况肯定包含了所有的边，所以后面的边肯定也无法使之连通。
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e3 + 5; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; struct node{ int u, v, val; node(int _u,int _v,int _val){ u = _u; v = _v; val = _val; } friend bool operator <(const node&a,const node&b){ return a.val < b.val; } }; vector<node> v; int fa[N], n, m; void init(){ for(int i = 0;i < N;i ++) fa[i] = i; } int Find(int k){ if(k != fa[k]) fa[k] = Find(fa[k]); return fa[k]; } void Merge(int x,int y){ int dx = Find(x); int dy = Find(y); if(dx != dy) fa[dy] = dx; } int main() { while(cin >> n >> m){ v.clear(); int tu,tv,tval; for(int i = 1;i <= m;i ++){ cin >> tu >> tv >> tval; v.push_back(node(tu,tv,tval)); } sort(v.begin(),v.end()); int ans=INF; int q, s, e; cin >> q; while(q --){ ans = INF; cin >> s >> e; for(int i = 0;i < m;i ++){ init(); for(int j = i;j < m;j ++){ Merge(v[j].v,v[j].u); if(Find(s) == Find(e)){ ans = min(ans,v[j].val - v[i].val); } } if(ans == INF) break; } printf("%d\n",ans==INF?-1:ans); } } return 0; }
