hdu1598 find the most comfortable road

找一条路，使路径中结点权最小和最大的差最小。

按权值从小到大排序，枚举起点终点，并查集判断要求的起点终点是否连通。

哎 好多麻烦题 就暴力暴力着思路就出来了

#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#define inf 0x3f3f3f3f
#define ll __int64
using namespace std;

int r[210],n,m;

struct node
{
    int s,e,w;
}v[1010];

bool cmp(node a,node b)
{
    return a.w<b.w;
}

int root(int a)
{
    if(r[a]==a) return a;
    r[a]=root(r[a]);
    return r[a];
}

void merge(int a,int b)
{
    int ra,rb;
    ra=root(a);
    rb=root(b);
    if(ra==rb) return ;
    if(ra<rb) r[ra]=rb;
    else r[rb]=ra;
}

int main()
{
    int i,j,x,y,ans,q;
    while(~scanf("%d%d",&n,&m))
    {
        for(i=0;i<m;i++)
            scanf("%d%d%d",&v[i].s,&v[i].e,&v[i].w);
        sort(v,v+m,cmp);
        scanf("%d",&q);
        while(q--)
        {
            scanf("%d%d",&x,&y);
            ans=inf;
            for(i=0;i<m;i++)
            {
                for(j=0;j<=n;j++)
                    r[j]=j;
                for(j=i;j<m;j++)
                {
                    merge(v[j].s,v[j].e);
                    if(root(x)==root(y))
                    {
                        if(v[j].w-v[i].w<ans)
                            ans=v[j].w-v[i].w;
                        break;
                    }
                }
            }
            if(ans==inf)
                printf("-1\n");
            else
                printf("%d\n",ans);
        }
    }
    return 0;
}

hdu1598 find the most comfortable road,布布扣,bubuko.com

hdu1598 find the most comfortable road

原文：http://blog.csdn.net/u011032846/article/details/21118597