中文题，题意就不说了
不过想不到并查集这样用
对于题目中的路，按速度进行排序，这样，如果从第 i 条路到第 j 条路之间的所有路能够让 i 和 j 连通，那么，这就存在一条路，且这条路的舒适度就是 两者的差值。 这样，只要枚举从每一条路开始，向前找到可以使得 起点和终点连通的路的舒适度，就可以找到答案了
View Code
#include<iostream>
#include<algorithm>
using namespace std;
struct edge
{
int u,v,w;
}e[1001];
int f[201],n,m;
bool cmp(edge a,edge b)
{
return a.w<b.w;
}
void init()
{
for(int i=0;i<=n;i++)
f[i]=i;
}
int find(int x)
{
if(x==f[x])
return f[x];
f[x]=find(f[x]);
return f[x];
}
void Union(int x,int y)
{
int a=find(x);
int b=find(y);
if(a==b)
return;
f[a]=b;
}
int main()
{
int Q;
while(scanf("%d %d",&n,&m)==2)
{
for(int i=0;i<m;i++)
scanf("%d %d %d",&e[i].u,&e[i].v,&e[i].w);
sort(e,e+m,cmp);
scanf("%d",&Q);
while(Q--)
{
int x,y;
int ans=INT_MAX;
scanf("%d %d",&x,&y);
for(int i=0;i<m;i++)
{
init();
int flag=0,k=0;
for(int j=i;j<m;j++)
{
// cout<<e[j].u<<' '<<e[j].v<<endl;
Union(e[j].u,e[j].v);
if(find(x)==find(y))
{
flag=1;
k=j;
break;
}
// cout<<find(x)<<' '<<find(y)<<endl;
}
if(!flag) break;
ans=min(ans,e[k].w-e[i].w);
}
if(ans==INT_MAX)
printf("-1\n");
else printf("%d\n",ans);
}
}
return 0;
}
不过更喜欢下面这种做法
二分枚举差值+最短路判断是否可达
View Code
#include"iostream"
#include"queue"
#include"algorithm"
#define MAXN 205
#define MAXM 2005
#define inf 0x3f3f3f3f
using namespace std;
struct ee
{
int u,v,c;
}edge[MAXM];
struct edges
{
int u,c,next;
}e[MAXM];
int N,M,idx;
int p[MAXN],dist[MAXN];
bool used[MAXN];
queue<int>q;
bool cmp(ee a,ee b)
{
return a.c<b.c;
}
void init()
{
idx=0;
memset(p,0xff,sizeof(p));
}
void addedge(int u,int v,int c)
{
e[idx].u=v;
e[idx].c=c;
e[idx].next=p[u];
p[u]=idx++;
}
void spfa(int s)
{
int t,u,w;
while(!q.empty())q.pop();
memset(used,false,sizeof(used));
for(int i=0;i<N;i++)
dist[i]=inf;
dist[s]=0;
q.push(s);
while(!q.empty())
{
t=q.front();
q.pop();
used[t]=false;
for(int i=p[t];i!=-1;i=e[i].next)
{
u=e[i].u;
w=e[i].c;
if(dist[t]+w<dist[u])
{
dist[u]=dist[t]+w;
if(!used[u])
{
used[u]=true;
q.push(u);
}
}
}
}
}
int main(){
int a,b,K,l,h,ll,hh,mid,low;
while(scanf("%d%d",&N,&M)==2)
{
for(int i=0;i<M;i++)
{
scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].c);
edge[i].u--;
edge[i].v--;
}
sort(edge,edge+M,cmp);
hh=edge[M-1].c-edge[0].c;
ll=inf;
for(int i=1;i<M;i++)
{
if(edge[i].c-edge[i-1].c<ll)
ll=edge[i].c-edge[i-1].c;
}
scanf("%d",&K);
bool flag=false;
int res=-1;
while(K--)
{
scanf("%d%d",&a,&b);
a--;b--;
l=ll,h=hh;
res=-1;
while(l<=h)//二分逼近满足条件的最小差值
{
flag=false;
mid=(l+h)>>1;
for(int i=0;i<M;i++)
{
low=edge[i].c;
init();
for(int j=i;j<M;j++)//选出所有满足当前差值的边
{
if(edge[j].c>low+mid)
break;
addedge(edge[j].u,edge[j].v,1);
addedge(edge[j].v,edge[j].u,1);
}
spfa(a);
if(dist[b]!=inf)//判断是否可达
{
flag=true;
break;
}
}
if(flag)
{
res=mid;
h=mid-1;
}
else l=mid+1;
}
printf("%d\n",res);
}
}
return 0;
}