当前位置: 代码迷 >> 综合 >> 1703 暴力摩托
  详细解决方案

1703 暴力摩托

热度:5   发布时间:2023-12-11 23:46:22.0

Problem : 暴力摩托
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 120 Solved: 62
[Submit][Status][Web Board]DescriptionN个站,之间连了M条双向的通路!但每条路都规定了一个速度的限制值,在这条路上必须以这个速度前进!所以在

前进的时候要调整速度,现决定尽量使调整的幅度小一些,也就是使走过的路的速度最大值与最小值之差最小!
Input第一行有2个正整数N , M , 分别表示站点数,路径数.

接下来M行,每行有3个正整数 X, Y, V表示X, Y之间有一条路,其Speed值是V。

再接下来是数K, 表示任务数,

下面K行,每行有一对正整数P,Q ,表示一个任务从P到Q.

(1<=n<=200, 1<=m<=1000, 1<=K<=10)
Output对于每一个任务输出一行,仅一个数,即最大速度与最小速度之差。
Sample Input
4 4
1 2 2
2 3 4
1 4 1
3 4 2
2
1 3
1 2
Sample Output
1
0

这一题可以用并查集做,一开始先要排序,这样的话之后找到了摩托可以走的路就不用去判断了,直接跳出循环,所以还要写一个cmp比较函数。然后就可以寻找当前x和y的根,如果没有连通,就把他们所在的分支连接,最后再判断一下最小值就可以输出了。

#include<bits/stdc++.h>
using namespace std;
struct node {int x,y,v;
} a[1001];
bool cmp(node a,node b) {return a.v<b.v;
}
int n,m,k,x,y,f[1001],fx,fy,ans=0x7fffffff;
int find(int x) {if(f[x]!=x)return f[x]=find(f[x]);
}
int main() {cin>>n>>m;for(int i=1; i<=m; i++)cin>>a[i].x>>a[i].y>>a[i].v;sort(a+1,a+m+1,cmp);cin>>k;for(int l=1; l<=k; l++) {int i,j;cin>>x>>y;ans=1e9;for(i=1; i<=m; i++) {for(j=0; j<=n; j++)f[j]=j;for(j=i; j<=m; j++) {fx=find(a[j].x);fy=find(a[j].y);if(fx!=fy)f[fx]=fy;if(find(x)==find(y))break;}if(f[x]==f[y])ans=min(ans,abs(a[j].v-a[i].v));}cout<<ans<<endl;}return 0;
}