https://www.bnuoj.com/v3/contest_show.php?cid=9146#problem/F
【题意】
给定n个城市和m条带权边，q次查询，问某两个城市之间的所有路径中最大边和最小边的差值最小是多少？
【思路】
首先给所有的边从小到大排序，然后枚举最小边，向右遍历各条边：查找这条边的两个端点是否连通，不连通就加入并查集，并且更新q个查询的答案；连通的话不进行任何操作
【Accetped】
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<algorithm> 5 #include<string> 6 #include<cstring> 7 8 using namespace std; 9 typedef long long ll; 10 typedef double db; 11 const int maxm=1e3+5; 12 const int inf=0x3f3f3f3f; 13 struct sars 14 { 15 int x; 16 int y; 17 int w; 18 bool operator<(const sars& t)const 19 { 20 return w<t.w; 21 } 22 }node[maxm]; 23 int n,m,q; 24 const int maxn=205; 25 int stt[15],ed[15],ans[15]; 26 int fa[maxn]; 27 int getfa(int x) 28 { 29 return x==fa[x]?x:fa[x]=getfa(fa[x]); 30 } 31 int main() 32 { 33 while(scanf("%d%d",&n,&m)!=EOF) 34 { 35 memset(ans,inf,sizeof(ans)); 36 for(int i=0;i<m;i++) 37 { 38 scanf("%d%d%d",&node[i].x,&node[i].y,&node[i].w); 39 } 40 sort(node,node+m); 41 scanf("%d",&q); 42 for(int i=0;i<q;i++) 43 { 44 scanf("%d%d",&stt[i],&ed[i]); 45 } 46 for(int i=0;i<m;i++) 47 { 48 for(int k=1;k<=n;k++) 49 { 50 fa[k]=k; 51 } 52 int mns=node[i].w; 53 for(int k=i;k<m;k++) 54 { 55 int u=node[k].x; 56 int v=node[k].y; 57 int w=node[k].w; 58 int x=getfa(u); 59 int y=getfa(v); 60 if(x!=y) 61 { 62 fa[x]=y; 63 for(int j=0;j<q;j++) 64 { 65 if(getfa(stt[j])==getfa(ed[j])) 66 { 67 ans[j]=min(ans[j],w-mns); 68 } 69 } 70 } 71 } 72 } 73 for(int i=0;i<q;i++) 74 { 75 if(ans[i]==inf) 76 { 77 printf("-1 "); 78 } 79 else 80 { 81 printf("%d ",ans[i]); 82 } 83 } 84 } 85 return 0; 86 }