Z小镇是一个景色宜人的地方，吸引来自各地的观光客来此旅游观光。
Z小镇附近共有
N(1<N≤500)个景点（编号为1,2,3,…,N），这些景点被M（0<M≤5000）条道路连接着，所有道路都是双向的，两个景点之间可能有多条道路。也许是为了保护该地的旅游资源，Z小镇有个奇怪的规定，就是对于一条给定的公路Ri，任何在该公路上行驶的车辆速度必须为Vi。频繁的改变速度使得游客们很不舒服，因此大家从一个景点前往另一个景点的时候，都希望选择行使过程中最大速度和最小速度的比尽可能小的路线，也就是所谓最舒适的路线。

第一行包含两个正整数，N和M。
接下来的M行每行包含三个正整数：x，y和v（1≤x,y≤N，0 最后一行包含两个正整数s，t，表示想知道从景点s到景点t最大最小速度比最小的路径。s和t不可能相同。

如果景点s到景点t没有路径，输出“IMPOSSIBLE”。否则输出一个数，表示最小的速度比。如果需要，输出一个最简分数。

N(1<N≤500)   M（0<M≤5000） Vi在int范围内

  最小生成树Kruskal的思路，按速度从小到大排序后，从速度最小的公路开始进行枚举，把每条路的两端放到同一个集合，判断此时起点是否能到达终点，更新最小值。另一道类似题：点我

#include<iostream> #include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int maxn = 5005;const int INF = 0x3f3f3f3f;int N,M,rk[maxn],father[maxn];struct Edge{	int u,v,w;}edge[maxn];bool cmp(struct Edge x,struct Edge y){	return x.w < y.w;}void init(){	memset(rk,0,sizeof(rk));	memset(father,0,sizeof(father));	for (int i = 0;i <= N;i++)	{		father[i] = i;	}}int find(int x){	int r = x;	while (r != father[r])	{		r = father[r];	}	int i = x,j;	while (i != r)	{		j = father[i];		father[i] = r;		i = j;	}	return r;}void unite(int x,int y){	x = find(x);	y = find(y);	if (x != y)	{		if (rk[x] < rk[y])		{			father[x] = y;		}		else		{			father[y] = x;			if (rk[x] == rk[y])			{				rk[x]++;			}		}	}}int gcd(int a,int b){	return b?gcd(b,a%b):a;}int main(){	while (~scanf("%d%d",&N,&M))	{		int s,t,fz,fm;		double res = INF;		for (int i = 0;i < M;i++)		{			scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);		}		scanf("%d%d",&s,&t);		sort(edge,edge + M,cmp);		for (int i = 0;i < M;i++)		{			init();			for (int j = i;j < M;j++)			{				unite(edge[j].u,edge[j].v);				if (find(s) == find(t))				{					double tmp = 1.0*edge[j].w/edge[i].w;					if (tmp < res)					{						res = tmp;						fz = edge[j].w;						fm = edge[i].w;					}				}			}		}		int com = gcd(fz,fm);		res == INF?printf("IMPOSSIBLE\n"):fm/com == 1?printf("%d\n",fz/com):printf("%d/%d\n",fz/com,fm/com);	}	return 0;}