思路：
考虑一个暴力：枚举最大的边权和最小的边权，然后将边权在这之间的边全拿出来构成一张无向图，剩下的就是判断是否存在一条从$S$到$T$的路径。
相当于判$S$和$T$是否连通，用并查集连一下即可。
时间复杂度：O(m³α(n))
考虑优化，枚举了最小边权之后，从小到大枚举最大边权，每次能新添加一条边。
因为并查集是支持动态加边的，所以复杂度就降到O(m²α(n))了。
一开始存边的vector忘记每次清零，一直Wrong Answer。
#include<cstdio>
#include<vector>
#include<algorithm>
const int inf=0x7fffffff;
struct Edge {
int from,to,w;
bool operator < (const Edge &x) const {
return w<x.w;
}
};
std::vector<Edge> e;
inline void add_edge(const int u,const int v,const int w) {
e.push_back((Edge){u,v,w});
}
const int N=;
class DisjointSet {
private:
int anc[N];
int Find(const int x) {
return x==anc[x]?x:anc[x]=Find(anc[x]);
}
public:
void reset(const int n) {
for(int i=;i<=n;i++) anc[i]=i;
}
bool isConnected(const int x,const int y) {
return Find(x)==Find(y);
}
void Union(const int x,const int y) {
anc[Find(x)]=Find(y);
}
};
DisjointSet s;
int main() {
int n,m;
while(~scanf("%d%d",&n,&m)) {
e.clear();
while(m--) {
int s,t,w;
scanf("%d%d%d",&s,&t,&w);
add_edge(s,t,w);
}
std::sort(e.begin(),e.end());
int q;
scanf("%d",&q);
while(q--) {
int S,T;
scanf("%d%d",&S,&T);
int ans=inf;
for(unsigned i=;i<e.size();i++) {
s.reset(n);
for(unsigned j=i;j<e.size();j++) {
int &u=e[j].from,&v=e[j].to;
if(!s.isConnected(u,v)) {
s.Union(u,v);
if(s.isConnected(S,T)) {
ans=std::min(ans,e[j].w-e[i].w);
break;
}
}
}
}
printf("%d\n",ans!=inf?ans:-);
}
}
return ;
}