HDU_1598 find the most comfortable road(二分+bfs)

　　/*用并查集做可以，不过总觉得别扭。明明是图论的题嘛。今天在师兄博客里看到这个
    解法，用二分限定所取的边的权值。设最大与最小差为lim，最小为low。所以low <= 
    weight <= low + lim；所以，用二分取到lim最小的一个。

ps:限定low时需与熬用到hash，否则直接存m个weight会TLE。不能抵达终点输出-1，我晕，因为这个错了好几次。。。T_T*/

//My Code： 234+MS

#include <iostream>
#include <cstdio>
#include <cstring>
#include <set>

using namespace std;

const int N = 10010;
const int inf = 10000000;

struct node {
    int to;
    int w;
    int next;
} e[N];

int t, num;
int q[N<<1], head[N],low[N];
bool vis[N], hash[1000001];

void add(int u, int v, int w) {
    e[t].to = v; e[t].w = w;
    e[t].next = head[u]; head[u] = t++;
}

bool bfs(int lim, int st, int ed) {
    int i, j, u, v;
    int f, r, l;
    for(i = 0; i < num; i++) {
        l = low[i]; q[0] = st;
        memset(vis, false, sizeof(vis));
        vis[st] = true; f = r = 0;
        while(f <= r) {
            u = q[f++];
            for(j = head[u]; j != -1; j = e[j].next) {
                v = e[j].to;
                if(!vis[v] && e[j].w >= l && e[j].w <= l + lim) {
                    if(v == ed)    return true;
                    vis[v] = true;
                    q[++r] = v;
                }
            }
        }
    }
    return false;
}

void solve(int st, int ed) {
    int l = 0, r = inf, mid, ans = -1;
    while(l <= r) {
        mid = (l + r) >> 1;
        if(bfs(mid, st, ed)) {
            ans = mid;
            r = mid - 1;
        }
        else    l = mid + 1;
    }
    printf("%d\n", ans);
}

int main() {
    //freopen("data.in", "r", stdin);

    int u, v, w, n, m, i, p;
    while(~scanf("%d%d", &n, &m)) {
        memset(head, -1, sizeof(head));
        memset(hash, false, sizeof(hash));
        memset(e, 0, sizeof(e));

        t = 0, num = 0;
        for( i = 0; i < m; i++) {
            scanf("%d%d%d", &u, &v, &w);
            if(!hash[w]) {
                hash[w] = true;
                low[num++] = w;
            }
            add(u, v, w);
            add(v, u, w);
        }
        scanf("%d", &p);
        while(p--) {
            scanf("%d%d", &u, &v);
            solve(u, v);
        }
    }
    return 0;
}