记录编号	160526	评测结果	AAAAAAAAAA
题目名称	[NOIP 2013]货车运输	最终得分	100
用户昵称	rpCardinal	是否通过	通过
代码语言	C++	运行时间	0.130 s
提交时间	2015-04-28 09:03:38	内存使用	4.74 MiB

#include <cstdio>
#include <climits>
#include <algorithm>
#define MM 17
using namespace std;

struct adlist
{
    int u[10010],v[20010],w[20010],p[20010],m;
    void insert(int x,int y,int z)
    {
        ++m; v[m]=y; w[m]=z; p[m]=u[x]; u[x]=m;
        ++m; v[m]=x; w[m]=z; p[m]=u[y]; u[y]=m;
    }
}g;

struct edge
{
    int x,y,z;
    bool operator<(edge B)const
    {return z>B.z;}
}E[100010];

struct djset
{
    int f[10010];
    void init(int n) {for (int i=1;i<=n;++i) f[i]=i;}
    int F(int x) {f[x]=f[x]==x?x:F(f[x]); return f[x];}
}S;

int p[MM][10010],h[10010],d[MM][10010];

void init(int x,int f,int dis)
{
    p[0][x]=f; d[0][x]=dis; h[x]=h[f]+1;
    for (int i=1;i<MM;++i) p[i][x]=p[i-1][p[i-1][x]];
    for (int i=1;i<MM;++i) d[i][x]=min(d[i-1][x],d[i-1][p[i-1][x]]);
    for (int i=g.u[x];i;i=g.p[i])
        if (g.v[i]!=f) init(g.v[i],x,g.w[i]);
}

int work(int x,int y)
{
    int ret=INT_MAX;
    if (h[x]<h[y]) swap(x,y); int dt=h[x]-h[y];
    for (int i=MM-1;i>=0;--i)
        if ((dt>>i)&1) {ret=min(ret,d[i][x]); x=p[i][x];}
    for (int i=MM-1;i>=0;--i)
        if (p[i][x]!=p[i][y])
        {
            ret=min(ret,d[i][x]); x=p[i][x];
            ret=min(ret,d[i][y]); y=p[i][y];
        }
    return x==y?ret:min(ret,min(d[0][x],d[0][y]));
}

int main()
{
    freopen("truck.in","r",stdin);
    freopen("truck.out","w",stdout);
    int n,m; scanf("%d%d",&n,&m);
    for (int i=1;i<=m;++i)
        scanf("%d%d%d",&E[i].x,&E[i].y,&E[i].z);
    sort(E+1,E+m+1); S.init(n);
    for (int i=1;i<=m;++i)
    {
        int fx=S.F(E[i].x),fy=S.F(E[i].y);
        if (fx==fy) continue; S.f[fy]=fx;
        g.insert(E[i].x,E[i].y,E[i].z);
    }
    for (int i=1;i<=n;++i) if (!h[i]) init(i,0,0);

    int q; scanf("%d",&q);
    while (q--)
    {
        int x,y; scanf("%d%d",&x,&y);
        if (S.F(x)==S.F(y))
            printf("%d\n",work(x,y));
        else
            printf("-1\n");
    }
    fclose(stdin); fclose(stdout);
    return 0;
}