【クラスクルーズ作り方+列挙最小辺】【HDU 1598】【find the most comfortable road】

タイトル:
 あなたに1つの図をあげて、辺権があって、K個は尋ねます:uからvまで のパス  辺の重みの最大値-辺の重みの最小値の最小値はいくらです
http://acm.hdu.edu.cn/showproblem.php?pid=1598
問題解(自分で考えない):エッジを最小エッジに並べ替え、クロスカールのようにANS値(F[i][j])の複雑度Q*E^2を更新し続けます 
Qが大きくなったらE*E*Nを選択して全ての点を前処理する
どうして自分で思わなかったの?あまりにも深さの考えで解决することにこだわって、このような辺権の最大値と最小値の问题は多く顺位を考虑すべきです
解法2:
二分差値、最小エッジを列挙し、クルーズカール
複雑度(Q*log(max-min)*E*E)
複雑さは明らかに解法に及ばない.
コード:

/*
WA1:        -1


*/
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#define oo 0x13131313
using namespace std;
struct Edge
{
    int s,t,w;
};
int n,m;
Edge A[1100];
int father[300];
void init()
{
    freopen("a.in","r",stdin);
    freopen("a.out","w",stdout);
}
void input()
{
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&A[i].s,&A[i].t,&A[i].w);
    }
}
void Clear()
{
     for(int i=1;i<=299;i++)
        father[i]=i;
}
bool cmp(Edge a,Edge b)
{
    return a.w<b.w;
}
int find(int x)
{
    if(x!=father[x])
    father[x]=find(father[x]);
    return father[x];
}
void Union(int a,int b)
{
    int aa=find(a),bb=find(b);
    father[aa]=bb;
}
void solve()
{
    sort(A+1,A+m+1,cmp);
    int Q,u,v;

    cin>>Q;
    for(int k=1;k<=Q;k++)
    {
        cin>>u>>v;
        int ok=0;
        int ans=100000000;
        for(int i=1;i<=m;i++)
            {
                Clear();
                for(int j=i;j<=m;j++)
                {
                    Union(A[j].s,A[j].t);
                    if(find(u)==find(v)) {
                                            ans=min(ans,A[j].w-A[i].w);
                                            break;
                                         }
                }
            }
        if(ans==100000000) printf("-1
");

        else  printf("%d
",ans);
    }
}
int main()
{
   // init();
    while(cin>>n>>m)
    {
        input();
        solve();
    }
}