贪心思想的Kruscal：先对边排序，再从第一条边开始，一旦start point 和 end poiont 连上，就break
1 #include <stdio.h> 2 #include <iostream> 3 #include <algorithm> 4 const int N = 1010; 5 const int inf = 1000000; 6 using namespace std; 7 8 struct Road{ 9 int st,ed,pd; //起点，终点、速度 10 }road[N]; 11 int cmp(const Road &p,const Road &q){ 12 return p.pd<q.pd; 13 } 14 int root[N]; 15 int n,m; 16 void init(){ 17 for(int i = 1; i <= n; i++){ 18 root[i] = -1; 19 } 20 } 21 int Find(int x){ 22 int s = x; 23 while(root[s] >= 0){ //一直查到parent[s]为负数（此时s为根结点)为止 24 s = root[s]; 25 } 26 while(s != x){ //路径压缩，优化，便于后续的查找操作加速 27 int temp = root[x]; 28 root[x] = s; 29 x=temp; 30 } 31 return s; 32 } 33 void Union(int R1,int R2){ 34 int r1 = Find(R1); 35 int r2 = Find(R2); 36 if(r1 != r2){ 37 root[r2] = r1; 38 } 39 } 40 int main(){ 41 int _case; 42 while(scanf("%d%d",&n,&m)!=EOF){ 43 for(int i = 1; i <= m; i++){ 44 scanf("%d%d%d",&road[i].st,&road[i].ed,&road[i].pd); 45 } 46 sort(road+1, road+1 + m, cmp); //calculating form 1 47 scanf("%d",&_case); 48 while(_case--){ 49 int st,ed; 50 int min = inf; 51 scanf("%d%d",&st,&ed); 52 for(int i = 1; i <= m; i++){ 53 init(); 54 for(int j = i; j <= m; j++){ 55 Union(road[j].st, road[j].ed); 56 if(Find(st) == Find(ed)){ 57 int ans = road[j].pd - road[i].pd; //舒适度 58 min = ans < min ? ans : min; 59 break; 60 } 61 } 62 } 63 if(min == inf) 64 printf("-1 "); 65 else 66 printf("%d ",min); 67 } 68 } 69 return 0; 70 }