cogs 1114. [郑州培训2012] 暴力摩托

★★☆ 输入文件：motor.in 输出文件：motor.out 简单对比
时间限制：1 s 内存限制：128 MB

MOTOR

题目描述

Fish最喜欢玩暴力摩托，一个通宵之后，总算过了全关！正当他为自己的成绩洋洋得意的时候却发现居然还有一个特别的附加关！Fish虽然累得眼睛都睁不开了，但是他还是决定再试一试！

这一关与以前的关不同，包含有N个站，之间连了M条双向的通路！但每条路都规定了一个Speed值，在这条路上必须以这个速度前进！所以在前进的时候要频繁的调整速度，这对鱼类来说是很痛苦的，所以Fish决定尽量使调整的幅度小一些，也就是使走过的路的速度最大值与最小值之差最小！

可最近Fish由于沉溺在暴力摩托中，已经荒废了编程技术，所以只有请你来帮忙了！

输入文件

第一行有2个正整数N，M，分别表示站点数，路径数。

接下来M行，每行有3个正整数 X, Y, V表示X， Y之间有一条路，其Speed值是V。再接下来是数K，表示任务数，下面K行，每行有一对正整数P，Q，表示一个任务从P到Q。

输出文件

对于每一个任务输出一行，仅一个数，即最大速度与最小速度之差。

样例

输入

4 4

1 2 2

2 3 4

1 4 1

3 4 2

1 3

1 2

输出

数据约定

1<=n<=200, 1<=m<=1000, 1<=K<=10

暴力并查集：

 1 #include<fstream>
 2 #include<algorithm>
 3 #include<cmath>
 4 #include<iostream>
 5 
 6 using namespace std;
 7 const int NN=1010;
 8 const int maxn=999999999;
 9 
10 struct node 
11 {
12     int u;
13     int v;
14     int w;
15 }E[NN];
16 
17 int F[1010];
18 int father[1010];
19 int N,M,K;
20 int MIN=maxn;
21 
22 bool CMP(node a,node b) 
23 {
24     if(a.w<=b.w)
25         return 1;
26     return 0;
27 }
28 
29 int Getfather(int v) 
30 {
31     if(father[v]==v)
32         return v;
33     return father[v]=Getfather(father[v]);
34 }
35 
36 inline int read()
37 {
38     int x=0,f=1;
39     char c=getchar();
40     while(c<'0'||c>'9') { if(c=='-') f=-1; c=getchar(); }
41     while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
42     return x*f;
43 }
44 
45 int main() 
46 {
47     freopen("motor.in","r",stdin);
48     freopen("motor.out","w",stdout);
49     N=read();
50     M=read();
51     int j;
52     for(int i=1; i<=M; i++)
53     {
54         E[i].u=read();
55         E[i].v=read();
56         E[i].w=read();
57     }
58     sort(E+1,E+M+1,CMP);
59     K=read();
60     for(int k=1; k<=K; k++) 
61     {
62         int x,y;
63         x=read();
64         y=read();
65         MIN=maxn;
66         for(int i=1; i<=M; i++) 
67         {
68             for(j=1; j<=N; j++)
69                 father[j]=j;
70             for(j=i; j<=M; j++) 
71             {
72                 int A=Getfather(E[j].u);
73                 int B=Getfather(E[j].v);
74                 if(A!=B)
75                     father[A]=B;
76                 if(Getfather(x)==Getfather(y))
77                     break;
78             }
79             if(E[j].w-E[i].w>=0)
80                 MIN=min(MIN,E[j].w-E[i].w);
81         }
82         printf("%d
",MIN);
83     }
84     return 0;
85 }